{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Atoms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countOfAtoms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #原子的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串化学式 <code>formula</code> ，返回 <strong>每种原子的数量</strong> 。</p>\n",
    "\n",
    "<p>原子总是以一个大写字母开始，接着跟随 0 个或任意个小写字母，表示原子的名字。</p>\n",
    "\n",
    "<p>如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"H2O\"</code> 和 <code>\"H2O2\"</code> 是可行的，但 <code>\"H1O2\"</code> 这个表达是不可行的。</li>\n",
    "</ul>\n",
    "\n",
    "<p>两个化学式连在一起可以构成新的化学式。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如 <code>\"H2O2He3Mg4\"</code> 也是化学式。</li>\n",
    "</ul>\n",
    "\n",
    "<p>由括号括起的化学式并佐以数字（可选择性添加）也是化学式。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如 <code>\"(H2O2)\"</code> 和 <code>\"(H2O2)3\"</code> 是化学式。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回所有原子的数量，格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>formula = \"H2O\"\n",
    "<strong>输出：</strong>\"H2O\"\n",
    "<strong>解释：</strong>原子的数量是 {'H': 2, 'O': 1}。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>formula = \"Mg(OH)2\"\n",
    "<strong>输出：</strong>\"H2MgO2\"\n",
    "<strong>解释：</strong>原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>formula = \"K4(ON(SO3)2)2\"\n",
    "<strong>输出：</strong>\"K4N2O14S4\"\n",
    "<strong>解释：</strong>原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= formula.length&nbsp;&lt;= 1000</code></li>\n",
    "\t<li><code>formula</code> 由英文字母、数字、<code>'('</code> 和 <code>')'</code> 组成</li>\n",
    "\t<li><code>formula</code> 总是有效的化学式</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-atoms](https://leetcode.cn/problems/number-of-atoms/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-atoms](https://leetcode.cn/problems/number-of-atoms/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"H2O\"', '\"Mg(OH)2\"', '\"K4(ON(SO3)2)2\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        # def dfs(l, mult1):\n",
    "        #     name = \"\"\n",
    "        #     cnt = 0\n",
    "        #     state = \"START\"\n",
    "        #     while l < n:\n",
    "        #         if formula[l] == \"(\":\n",
    "        #             if state != \"START\":\n",
    "        #                 ret[name] += max(1, cnt)*mult1\n",
    "        #                 cnt = 0\n",
    "        #                 name = \"\"\n",
    "        #                 state = \"START\"\n",
    "\n",
    "        #             tmp1 = l\n",
    "        #             tmp2 = r-1\n",
    "        #             while formula[tmp2] != \")\":\n",
    "        #                 tmp2 -= 1\n",
    "\n",
    "        #             l = tmp2\n",
    "        #             mult2 = 0\n",
    "        #             while l+1 < n and formula[l+1].isdigit():\n",
    "        #                 mult2 *= 10\n",
    "        #                 mult2 += int(formula[l+1])\n",
    "        #                 l += 1\n",
    "        #             print(l, r, tmp1, tmp2, mult2, formula[tmp1+1:tmp2])\n",
    "        #             dfs(tmp1+1, tmp2, mult1*max(mult2, 1))\n",
    "\n",
    "        #         elif formula[l].isdigit():\n",
    "        #             state = \"INT\"\n",
    "        #             cnt *= 10\n",
    "        #             cnt += int(formula[l])\n",
    "\n",
    "        #         else:\n",
    "        #             if state != \"START\" and formula[l].upper() == formula[l]:\n",
    "        #                 ret[name] += max(cnt, 1)*mult1\n",
    "        #                 name = \"\"\n",
    "        #                 cnt = 0\n",
    "        #             state = \"STR\"\n",
    "        #             name += formula[l]\n",
    "        #             # if name == \")\":\n",
    "        #             #     print(formula[l:r], l, r, \"ohohoho\")\n",
    "\n",
    "        #         l += 1\n",
    "\n",
    "        #     if name:\n",
    "        #         ret[name] += max(cnt, 1)*mult1\n",
    "                \n",
    "\n",
    "        # ret = defaultdict(lambda: 0)\n",
    "        n = len(formula)\n",
    "        stack = [defaultdict(lambda: 0)]\n",
    "        prev = None\n",
    "        idx = 0\n",
    "        name, cnt = \"\", 0\n",
    "        # while idx < n:\n",
    "        for idx in range(n):\n",
    "            if formula[idx].isalpha():\n",
    "                if not name or formula[idx].upper() != formula[idx]: \n",
    "                    name += formula[idx]\n",
    "                elif name:\n",
    "                    stack[-1][name] += max(cnt, 1)\n",
    "                    name = \"\"\n",
    "                    cnt = 0\n",
    "                    name = formula[idx]\n",
    "                if prev:\n",
    "                    for key, value in prev.items():\n",
    "                        stack[-1][key] += max(cnt, 1)*value\n",
    "                    prev = None\n",
    "                    cnt = 0\n",
    "            elif formula[idx] == \"(\":\n",
    "                if name:\n",
    "                    stack[-1][name] += max(cnt, 1)\n",
    "                    name = \"\"\n",
    "                    cnt = 0\n",
    "                elif prev:\n",
    "                    for key, value in prev.items():\n",
    "                        stack[-1][key] += max(cnt, 1)*value\n",
    "                    prev = None\n",
    "                    cnt = 0\n",
    "                stack.append(defaultdict(lambda: 0))\n",
    "            elif formula[idx].isdigit():\n",
    "                cnt *= 10\n",
    "                cnt += int(formula[idx])\n",
    "            elif formula[idx] == \")\":\n",
    "                if name:\n",
    "                    stack[-1][name] += max(cnt, 1)\n",
    "                    name = \"\"\n",
    "                    cnt = 0\n",
    "                elif prev:\n",
    "                    for key, value in prev.items():\n",
    "                        stack[-1][key] += max(cnt, 1)*value\n",
    "                    prev = None\n",
    "                    cnt = 0\n",
    "                prev = stack.pop()\n",
    "        if name:\n",
    "            stack[-1][name] += max(cnt, 1)\n",
    "            name = \"\"\n",
    "            cnt = 0\n",
    "        elif prev:\n",
    "            for key, value in prev.items():\n",
    "                stack[-1][key] += max(cnt, 1)*value\n",
    "            prev = None\n",
    "            cnt = 0\n",
    "        res = []\n",
    "        for key, value in stack[-1].items():\n",
    "            v = key+str(value) if value != 1 else key\n",
    "            res.append(v)\n",
    "        res = sorted(res)\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "\n",
    "        def dfs(formula, idx):\n",
    "            wd = {}\n",
    "            while idx < len(formula):\n",
    "                if formula[idx] == '(':\n",
    "                    sub_wd, idx = dfs(formula, idx + 1)\n",
    "                    for k, v in sub_wd.items():\n",
    "                        wd[k] = wd.get(k, 0) + v\n",
    "                elif formula[idx] == ')':\n",
    "                    idx += 1\n",
    "                    c = 0\n",
    "                    while idx < len(formula) and formula[idx].isdigit():\n",
    "                        c = c * 10 + int(formula[idx])\n",
    "                        idx += 1\n",
    "                    c = max(c, 1)\n",
    "                    for k, v in wd.items():\n",
    "                        wd[k] = v * c\n",
    "                    break\n",
    "                else:\n",
    "                    s = idx\n",
    "                    idx += 1\n",
    "                    while idx < len(formula) and formula[idx].islower():\n",
    "                        idx += 1\n",
    "                    k = formula[s:idx]\n",
    "                    c = 0\n",
    "                    while idx < len(formula) and formula[idx].isdigit():\n",
    "                        c = c * 10 + int(formula[idx])\n",
    "                        idx += 1\n",
    "                    c = max(c, 1)\n",
    "                    wd[k] = wd.get(k, 0) + c\n",
    "            return wd, idx\n",
    "\n",
    "        wd, _ = dfs(formula, 0)\n",
    "        return ''.join([k + (str(v) if v > 1 else '') for k, v in sorted(wd.items(), key=lambda x: x[0])])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 执行用时：36 ms, 在所有 Python3 提交中击败了90.12%的用户\n",
    "# 内存消耗：15.2 MB, 在所有 Python3 提交中击败了8.72%的用户\n",
    "import re\n",
    "class Solution:\n",
    "    pt=re.compile(\"([A-Z][a-z]*)|([()])|(\\d+)\")  # 用正则表达式将 formula 分为元素、左右括号和数字分为三类\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        formula=tuple(filter(bool,re.split(self.pt,formula)))   # 将 formula 按元素、左右括号和数字之间分隔为字符串数组\n",
    "        # print(formula)\n",
    "        total=defaultdict(int)  # 统计所有原子个数的字典\n",
    "        stack=[1,]  # 用来递归括号的栈，先把整个式子当成是在一个括号内。其元素为\"重复倍数\"。\n",
    "        num=1       # 局部（当前括号内的）个数，因为不写个数就是1个，故初值为1。\n",
    "        for a in formula[::-1]:\n",
    "            if a.isdigit():    # a是数字：当左边是元素则num为局部原子个数；当左边是括号则num为该括号对的重复倍数。\n",
    "                num=int(a)\n",
    "            else:\n",
    "                mul=stack[-1]    # 取当前（括号内）的：重复倍数、统计字典。\n",
    "                if a.isalpha(): # a是元素符号：要加上 重复倍数×局部原子个数 个。\n",
    "                    total[a] += mul*num\n",
    "                elif ')'==a:    # 是右括号（注意是逆序遍历）入栈。则num是新括号内的重复倍数，则要和总的重复倍数相乘。\n",
    "                    stack.append(mul*num)\n",
    "                elif '('==a:    # 是左括号，将此对括号内的统计结果汇总到括号外。然后出栈。\n",
    "                    stack.pop() # cur_dict已经引用了，故pop不会导致统计结果丢失。\n",
    "                num=1   # ★易错！局部个数用了一次之后就要重置为1，如果是括号的重复倍数，则已经入栈记录了。\n",
    "        return ''.join(key+(str(val) if val>1 else '')              # 注意原子个数为1，则省略为''。最后用''作为分隔符连接所有字符串\n",
    "                       for key,val in sorted(total.items()))  # 要以元素字典序升序排序。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "where = 0\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        ans = self.dfs(formula, 0)\n",
    "        # print(ans)\n",
    "        res = ''\n",
    "        for key, val in sorted(ans.items()):\n",
    "            if val > 1:\n",
    "                res += key + str(val)\n",
    "            else:\n",
    "                res += key\n",
    "        return res\n",
    "\n",
    "    def dfs(self, s, i):\n",
    "        global where\n",
    "        ans = collections.defaultdict(int)\n",
    "        name = ''\n",
    "        pre = collections.defaultdict(int)\n",
    "        cnt = 0\n",
    "        while i < len(s) and s[i] != ')':\n",
    "            if 'A' <= s[i] <= 'Z' or s[i] == '(':\n",
    "                self.fill(ans, name, pre, cnt)\n",
    "                pre = collections.defaultdict(int)\n",
    "                name = ''\n",
    "                cnt = 0\n",
    "                if 'A' <= s[i] <= 'Z':\n",
    "                    name += s[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    pre = self.dfs(s, i+1)\n",
    "                    i = where + 1\n",
    "            elif 'a' <= s[i] <= 'z':\n",
    "                name += s[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                cnt = cnt * 10 + int(s[i])\n",
    "                i += 1\n",
    "        self.fill(ans, name, pre, cnt)\n",
    "        where = i \n",
    "        return ans\n",
    "    \n",
    "    def fill(self, ans, name, pre, cnt):\n",
    "        # if len(name) > 0 or len(pre) != 0:\n",
    "        if len(name) > 0 or pre != {}:\n",
    "            cnt = 1 if cnt == 0 else cnt\n",
    "            if len(name) > 0:\n",
    "                ans[name] += cnt\n",
    "            else:\n",
    "                for key in pre.keys():\n",
    "                    ans[key] += pre[key] * cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stk = [1]\n",
    "        name = num = ''\n",
    "        c = Counter()\n",
    "        for f in formula[::-1]:\n",
    "            if 'A' <= f <= 'Z':\n",
    "                c[f+name] += stk[-1] * int(num or '1')\n",
    "                name = num = ''\n",
    "            elif 'a' <= f <= 'z':\n",
    "                name = f + name\n",
    "            elif '0' <= f <= '9':\n",
    "                num = f + num\n",
    "            elif f == '(':\n",
    "                stk.pop()\n",
    "            elif f == ')':\n",
    "                stk.append(stk[-1]*int(num or '1'))\n",
    "                num = ''\n",
    "        res = ''\n",
    "        for k, v in sorted(c.items()):\n",
    "            res += k if v == 1 else k+str(v)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "where = 0\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        ans = self.dfs(formula, 0)\n",
    "        # print(ans)\n",
    "        res = ''\n",
    "        for key, val in sorted(ans.items()):\n",
    "            if val > 1:\n",
    "                res += key + str(val)\n",
    "            else:\n",
    "                res += key\n",
    "        return res\n",
    "\n",
    "    def dfs(self, s, i):\n",
    "        global where\n",
    "        # 保存总的函数结果\n",
    "        ans = collections.defaultdict(int)\n",
    "        # 保存下次递归之前遇到的字母\n",
    "        name = ''\n",
    "        # 保存上一次递归的结果\n",
    "        pre = collections.defaultdict(int)\n",
    "        # 保存数字,即字母出现的次数\n",
    "        cnt = 0\n",
    "        while i < len(s) and s[i] != ')':\n",
    "            # 遇到大写字母或者(,说明要开始新一轮的计数\n",
    "            # 将之前的递归历史记录fill,并清空进行下一轮统计\n",
    "            if 'A' <= s[i] <= 'Z' or s[i] == '(':\n",
    "                self.fill(ans, name, pre, cnt)\n",
    "                pre = collections.defaultdict(int)\n",
    "                name = ''\n",
    "                cnt = 0\n",
    "                # 遇到大写字母,保存到name\n",
    "                if 'A' <= s[i] <= 'Z':\n",
    "                    name += s[i]\n",
    "                    i += 1\n",
    "                # 遇到左括号\n",
    "                else:\n",
    "                    pre = self.dfs(s, i+1)\n",
    "                    i = where + 1\n",
    "            # 遇到小写字母\n",
    "            elif 'a' <= s[i] <= 'z':\n",
    "                name += s[i]\n",
    "                i += 1\n",
    "            # 遇到数字\n",
    "            else:\n",
    "                cnt = cnt * 10 + int(s[i])\n",
    "                i += 1\n",
    "        # 上一轮递归完成返回结果,将之前保存的历史统计fill到ans中\n",
    "        self.fill(ans, name, pre, cnt)\n",
    "        where = i \n",
    "        return ans\n",
    "    \n",
    "    def fill(self, ans, name, pre, cnt):\n",
    "        # if len(name) > 0 or len(pre) != 0:\n",
    "        if len(name) > 0 or pre != {}:\n",
    "            cnt = 1 if cnt == 0 else cnt\n",
    "            if len(name) > 0:\n",
    "                ans[name] += cnt\n",
    "            else:\n",
    "                for key in pre.keys():\n",
    "                    ans[key] += pre[key] * cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stack = [1]\n",
    "        dic = collections.defaultdict(int)\n",
    "        count = lower = \"\"\n",
    "        i = len(formula) - 1\n",
    "        while i > -1:\n",
    "            if '0' <= formula[i] <= '9':\n",
    "                count = formula[i] + count\n",
    "            elif 'a' <= formula[i] <= 'z':\n",
    "                lower = formula[i] + lower\n",
    "            elif formula[i] == ')':\n",
    "                stack.append(stack[-1] * int(count or '1'))\n",
    "                count = ''\n",
    "            elif formula[i] == '(':\n",
    "                stack.pop()\n",
    "            elif 'A' <= formula[i] <= 'Z':\n",
    "                dic[formula[i] + lower] += stack[-1] * int(count or '1')\n",
    "                lower = \"\"\n",
    "                count = \"\"\n",
    "            i -= 1\n",
    "        ans = \"\"\n",
    "        for k, v in sorted(dic.items()):\n",
    "            if v == 1:\n",
    "                ans += k\n",
    "            else:\n",
    "                ans += k + str(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parse_name(self, s, i):\n",
    "        j = i + 1\n",
    "        while j < len(s) and s[j].islower():\n",
    "            j += 1\n",
    "        return s[i:j], j\n",
    "    def parse_num(self, s, i):\n",
    "        j = i\n",
    "        while j < len(s) and s[j].isnumeric():\n",
    "            j += 1\n",
    "        num = s[i:j]\n",
    "        if not num:\n",
    "            return 1, j\n",
    "        return int(num), j\n",
    "    def parse_expr(self, s, i):\n",
    "        atom_cnt = defaultdict(int)\n",
    "        while i < len(s) and s[i] != ')':\n",
    "            if s[i].isupper():\n",
    "                atom, i = self.parse_name(s, i)\n",
    "                num, i = self.parse_num(s, i)\n",
    "                atom_cnt[atom] += num\n",
    "            elif s[i] == '(':\n",
    "                subcnt, i = self.parse_expr(s, i+1)\n",
    "                num, i = self.parse_num(s, i)\n",
    "                subcnt = {k: v*num for k, v in subcnt.items()}\n",
    "                for k, v in subcnt.items():\n",
    "                    atom_cnt[k] += v        \n",
    "        return atom_cnt, i+1\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        atom_cnt, _ = self.parse_expr(formula, 0)\n",
    "        atom_nums = sorted([k+str(v) if v > 1 else k for k, v in atom_cnt.items()])\n",
    "        return ''.join(atom_nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        ## 输入当前遍历到的字符串的下标，输出遍历结束后的位置和一个count\n",
    "        def helper(i):\n",
    "            num, count = 0, defaultdict(int)\n",
    "            while i < len(formula):\n",
    "                ch = formula[i]\n",
    "                ## 如果遇到大写的，说明是一个新的原子，先收集原子名字，随后再尝试收集\n",
    "                if ch.isupper():\n",
    "                    ## 从当前i的下一位开始收集(一直收集小写字母)\n",
    "                    j = i + 1\n",
    "                    while j < len(formula) and formula[j].islower():\n",
    "                        j+=1\n",
    "                    atom_name = formula[i:j]\n",
    "\n",
    "                    ## 随后收集可能的数字，初始化num为1\n",
    "                    num = 0\n",
    "                    while j < len(formula) and formula[j].isdigit():\n",
    "                        num = num * 10 + int(formula[j])\n",
    "                        j += 1\n",
    "                    num = max(num, 1)\n",
    "                    count[atom_name] += num\n",
    "                    i = j\n",
    "                ## 遇到左括号，\n",
    "                elif formula[i] == '(':\n",
    "                    i, sub_count = helper(i+1)\n",
    "                    i+=1\n",
    "                    num = 0\n",
    "                    while i < len(formula) and formula[i].isdigit():\n",
    "                        num = 10 * num + int(formula[i])\n",
    "                        i+=1\n",
    "                    num = max(1, num)\n",
    "                    for atom, cnt in sub_count.items():\n",
    "                        count[atom] += num * cnt\n",
    "                elif ch == ')':\n",
    "                    return i,count\n",
    "            return i,count\n",
    "        i,count = helper(0)\n",
    "        ans = []\n",
    "        for atom in sorted(count):\n",
    "            if count[atom] > 1:\n",
    "                ans.append(str(atom)+str(count[atom]))\n",
    "            else:\n",
    "                ans.append(str(atom))\n",
    "        return \"\".join(ans)\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 执行用时：36 ms, 在所有 Python3 提交中击败了90.12%的用户\n",
    "# 内存消耗：15.2 MB, 在所有 Python3 提交中击败了8.72%的用户\n",
    "import re\n",
    "class Solution:\n",
    "    pt=re.compile(\"([A-Z][a-z]*)|([()])|(\\d+)\")  # 用正则表达式将 formula 分为元素、左右括号和数字分为三类\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        formula=tuple(filter(bool,re.split(self.pt,formula)))   # 将 formula 按元素、左右括号和数字之间分隔为字符串数组\n",
    "        # print(formula)\n",
    "        total=defaultdict(int)  # 统计所有原子个数的字典\n",
    "        stack=[1,]  # 用来递归括号的栈，先把整个式子当成是在一个括号内。其元素为\"重复倍数\"。\n",
    "        num=1       # 局部（当前括号内的）个数，因为不写个数就是1个，故初值为1。\n",
    "        for a in formula[::-1]:\n",
    "            if a.isdigit():    # a是数字：当左边是元素则num为局部原子个数；当左边是括号则num为该括号对的重复倍数。\n",
    "                num=int(a)\n",
    "            else:\n",
    "                mul=stack[-1]    # 取当前（括号内）的：重复倍数、统计字典。\n",
    "                if a.isalpha(): # a是元素符号：要加上 重复倍数×局部原子个数 个。\n",
    "                    total[a] += mul*num\n",
    "                elif ')'==a:    # 是右括号（注意是逆序遍历）入栈。则num是新括号内的重复倍数，则要和总的重复倍数相乘。\n",
    "                    stack.append(mul*num)\n",
    "                elif '('==a:    # 是左括号，将此对括号内的统计结果汇总到括号外。然后出栈。\n",
    "                    stack.pop() # cur_dict已经引用了，故pop不会导致统计结果丢失。\n",
    "                num=1   # ★易错！局部个数用了一次之后就要重置为1，如果是括号的重复倍数，则已经入栈记录了。\n",
    "        return ''.join(key+(str(val) if val>1 else '')              # 注意原子个数为1，则省略为''。最后用''作为分隔符连接所有字符串\n",
    "                       for key,val in sorted(total.items()))  # 要以元素字典序升序排序。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "\n",
    "        def dfs(s):\n",
    "            ans = defaultdict(int)\n",
    "            if not s:\n",
    "                return ans\n",
    "            i = 0\n",
    "            while i < len(s):\n",
    "                if s[i].isupper():\n",
    "                    j = i + 1\n",
    "                    while j < len(s) and s[j].islower():\n",
    "                        j += 1\n",
    "                    key = s[i:j]\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t*10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(1,t)\n",
    "                    ans[key] += t\n",
    "                    i = j\n",
    "                else:\n",
    "                    j,cnt = i + 1,1\n",
    "                    while cnt:\n",
    "                        if s[j] == '(':\n",
    "                            cnt += 1\n",
    "                        if s[j] == ')':\n",
    "                            cnt -= 1\n",
    "                        j += 1\n",
    "                    nxt = dfs(s[i + 1:j - 1])\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t*10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(1,t)\n",
    "                    for k,v in nxt.items():\n",
    "                        ans[k] += v*t\n",
    "                    i = j\n",
    "            return ans\n",
    "        \n",
    "        ans = ''\n",
    "        for k,v in sorted(dfs(formula).items()):\n",
    "            ans += k if v == 1 else k + str(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stack = [collections.defaultdict(int)]\n",
    "        i = 0\n",
    "\n",
    "        def parseInt():\n",
    "            nonlocal i \n",
    "\n",
    "            start = i\n",
    "            while i < len(formula) and formula[i].isdigit():\n",
    "                i += 1\n",
    "            \n",
    "            ss = formula[start:i]\n",
    "\n",
    "            if not ss:\n",
    "                return 1\n",
    "            else:\n",
    "                return int(ss)\n",
    "\n",
    "        def parseAtom():\n",
    "            nonlocal i\n",
    "            start = i \n",
    "            # while i < len(formula) and ('a' <= formula[i] <= 'z' or 'A' <= formula[i] <= 'Z'):\n",
    "            #     i += 1\n",
    "\n",
    "            # ss = formula[start:i]\n",
    "            i += 1\n",
    "            while i < len(formula) and 'a' <= formula[i] <= 'z':\n",
    "                i += 1\n",
    "            \n",
    "            ss = formula[start:i]\n",
    "\n",
    "            return ss \n",
    "\n",
    "        while i < len(formula):\n",
    "            if formula[i] == '(':\n",
    "                stack.append(collections.defaultdict(int))\n",
    "                i += 1\n",
    "            elif formula[i] == ')':\n",
    "                i += 1\n",
    "                mul = parseInt()\n",
    "\n",
    "                tmp = stack.pop()\n",
    "                for key in tmp.keys():\n",
    "                    stack[-1][key] += (tmp[key] * mul)\n",
    "\n",
    "            elif 'A' <= formula[i] <= 'Z':\n",
    "                atom = parseAtom()\n",
    "                cnt = parseInt()\n",
    "\n",
    "                tmp = stack[-1]\n",
    "                tmp[atom] = tmp.get(atom, 0) + cnt\n",
    "        \n",
    "        cnts = stack[0]\n",
    "\n",
    "        keys = sorted(cnts.keys())\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for key in keys:\n",
    "            res.append(key)\n",
    "            if cnts[key] != 1:\n",
    "                res.append(str(cnts[key]))\n",
    "        \n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        st,i,j=[{}],0,0\n",
    "        while True:\n",
    "            if formula[i]=='(':st.append({})\n",
    "            elif formula[i]!=')':\n",
    "                while j+1<len(formula) and formula[j+1].islower():j+=1\n",
    "                a,i=formula[i:j+1],j\n",
    "                while j+1<len(formula) and formula[j+1].isdigit():j+=1\n",
    "                n,i=formula[i+1:j+1],j\n",
    "                n=1 if n=='' else int(n)\n",
    "                if a in st[-1]:st[-1][a]+=n\n",
    "                else:st[-1][a]=n\n",
    "            else:\n",
    "                while j+1<len(formula) and formula[j+1].isdigit():j+=1\n",
    "                n,i=formula[i+1:j+1],j\n",
    "                n=1 if n=='' else int(n)\n",
    "                ss=st.pop()\n",
    "                for x,a in enumerate(ss):\n",
    "                    if a in st[-1]:st[-1][a]+=ss[a]*n\n",
    "                    else:st[-1][a]=ss[a]*n\n",
    "            i=j=i+1\n",
    "            if i==len(formula):break\n",
    "        al,r=list(st[-1].keys()),''\n",
    "        al.sort()\n",
    "        for a in al:r+=a+(str(st[-1][a]) if st[-1][a]>1 else '')\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "where = 0\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        d = self.dfs(formula, 0)\n",
    "        # print(d)\n",
    "        ans = ''\n",
    "        for key, val in sorted(d.items()):\n",
    "            # 要加括号\n",
    "            ans += key + (str(val) if val > 1 else '')\n",
    "            # if val > 1:\n",
    "            #     res += key + str(val)\n",
    "            # else:\n",
    "            #     res += key\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, s, i):\n",
    "        global where\n",
    "        # 保存总的函数结果\n",
    "        ans = collections.defaultdict(int)\n",
    "        # 保存下次递归之前遇到的字母\n",
    "        name = ''\n",
    "        # 保存上一次递归的结果\n",
    "        pre = collections.defaultdict(int)\n",
    "        # 保存数字,即字母出现的次数\n",
    "        cnt = 0\n",
    "        while i < len(s) and s[i] != ')':\n",
    "            # 遇到大写字母或者(,说明要开始新一轮的计数\n",
    "            # 将之前的递归历史记录fill,并清空进行下一轮统计\n",
    "            if 'A' <= s[i] <= 'Z' or s[i] == '(':\n",
    "                self.fill(ans, name, pre, cnt)\n",
    "                pre = collections.defaultdict(int)\n",
    "                name = ''\n",
    "                cnt = 0\n",
    "                # 遇到大写字母,保存到name\n",
    "                if 'A' <= s[i] <= 'Z':\n",
    "                    name += s[i]\n",
    "                    i += 1\n",
    "                # 遇到左括号\n",
    "                else:\n",
    "                    pre = self.dfs(s, i+1)\n",
    "                    i = where + 1\n",
    "            # 遇到小写字母\n",
    "            elif 'a' <= s[i] <= 'z':\n",
    "                name += s[i]\n",
    "                i += 1\n",
    "            # 遇到数字\n",
    "            else:\n",
    "                cnt = cnt * 10 + int(s[i])\n",
    "                i += 1\n",
    "        # 上一轮递归完成返回结果,将之前保存的历史统计fill到ans中\n",
    "        self.fill(ans, name, pre, cnt)\n",
    "        where = i \n",
    "        return ans\n",
    "    \n",
    "    def fill(self, ans, name, pre, cnt):\n",
    "        # if len(name) > 0 or len(pre) != 0:\n",
    "        if len(name) > 0 or pre != {}:\n",
    "            cnt = 1 if cnt == 0 else cnt\n",
    "            if len(name) > 0:\n",
    "                ans[name] += cnt\n",
    "            else:\n",
    "                for key in pre.keys():\n",
    "                    ans[key] += pre[key] * cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        \n",
    "        stack, atom, count, i = [], '', 0, 0\n",
    "        atom_count = collections.defaultdict(int)\n",
    "    \n",
    "\n",
    "\n",
    "        while i < len(formula):\n",
    "            if formula[i] == '(':\n",
    "                stack.append(atom_count)\n",
    "                atom_count = collections.defaultdict(int)\n",
    "                i += 1\n",
    "            elif formula[i] == ')':\n",
    "                i += 1\n",
    "                start = i\n",
    "                while i < len(formula) and formula[i].isdigit():\n",
    "                    i += 1\n",
    "                multiplier = int(formula[start:i] or 1)\n",
    "                tmp = atom_count\n",
    "                atom_count = stack.pop()\n",
    "                for key in tmp:\n",
    "                    atom_count[key] += tmp[key] * multiplier\n",
    "            else:\n",
    "                start = i\n",
    "                i += 1\n",
    "                while i < len(formula) and formula[i].islower():\n",
    "                    i += 1\n",
    "                atom = formula[start:i]\n",
    "                start = i\n",
    "                while i < len(formula) and formula[i].isdigit():\n",
    "                    i += 1\n",
    "                count = int(formula[start:i] or 1)\n",
    "                atom_count[atom] += count\n",
    "\n",
    "        output = []\n",
    "        for atom in sorted(atom_count):\n",
    "            output.append(atom)\n",
    "            if atom_count[atom] > 1:\n",
    "                output.append(str(atom_count[atom]))\n",
    "        return ''.join(output)\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    ch = formula[pose]\n",
    "    assert ch.isupper()\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #有小写\n",
    "    while  i<len(formula) and formula[i].islower():\n",
    "        i+=1\n",
    "    element = formula[pose:i]\n",
    "    #有数字\n",
    "    start_num = i\n",
    "    while i<len(formula) and formula[i].isdigit():\n",
    "        i += 1\n",
    "        flag = True\n",
    "    if flag:\n",
    "        if element not in dic:\n",
    "            dic[element] = int(formula[start_num:i])\n",
    "        else:\n",
    "            dic[element] += int(formula[start_num:i])\n",
    "    else:\n",
    "        if element not in dic:\n",
    "            dic[element] = 1\n",
    "        else:\n",
    "            dic[element] += 1\n",
    "    return i\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose, dic\n",
    "\n",
    "        ch = formula[pose]\n",
    "        if ch == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            assert formula[pose] == ')'\n",
    "            pose+=1\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose += 1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose, dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        assert pos == len(formula)\n",
    "        lst = sorted(dic.items(), key=lambda x: x[0])\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        # 倒着的时候， 记录map，乘的基数，迭代中的乘数，个数，个数的10进制位数，元素\n",
    "        cnts, multiply, muls, num, num_count, atom = defaultdict(int), 1, [], 0, 0, \"\"\n",
    "        for c in formula[::-1]:\n",
    "            if c == ')':\n",
    "                # 如果当前有统计的数字，乘的基数要叠加\n",
    "                if num:\n",
    "                    multiply *= num\n",
    "                    muls.append(num)\n",
    "                    num = num_count = 0\n",
    "                else:\n",
    "                    muls.append(1)\n",
    "            elif c == '(':\n",
    "                # 去除掉上一个乘数\n",
    "                multiply //= muls.pop()\n",
    "            elif str.isdigit(c):\n",
    "                num += int(c) * (10 ** num_count)\n",
    "                num_count += 1\n",
    "            elif str.islower(c):\n",
    "                atom += c\n",
    "            else:\n",
    "                atom += c\n",
    "                # 注意我们在更新元素个数时，始终要考虑乘的基数\n",
    "                if num:\n",
    "                    cnts[atom[::-1]] += num * multiply\n",
    "                else:\n",
    "                    cnts[atom[::-1]] += multiply\n",
    "                atom = \"\"\n",
    "                num = num_count = 0\n",
    "        return \"\".join(key if cnts[key] == 1 else key + str(cnts[key]) for key in sorted(cnts.keys()))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#栈，类似字符串转换。栈里面存字典\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stack=[]\n",
    "        stack.append(defaultdict(int))\n",
    "        self.i,self.n=0,len(formula)\n",
    "        def get_atom():\n",
    "            # atom=''\n",
    "            # atom+=formula[self.i]\n",
    "            atom=formula[self.i]\n",
    "            self.i+=1\n",
    "            while self.i<self.n and formula[self.i].islower():\n",
    "                atom+=formula[self.i]\n",
    "                self.i+=1\n",
    "            return atom\n",
    "        def get_num():\n",
    "            res=''\n",
    "            while self.i<self.n and formula[self.i].isnumeric():\n",
    "                res+=formula[self.i]\n",
    "                self.i+=1\n",
    "            return 1 if res==''else int(res)\n",
    "        while self.i<self.n:\n",
    "            ch=formula[self.i]\n",
    "            if ch=='(':\n",
    "                stack.append(defaultdict(int))\n",
    "                self.i+=1\n",
    "            elif ch==')':\n",
    "                self.i+=1\n",
    "                num=get_num()\n",
    "                maps=stack.pop()\n",
    "                for k,v in maps.items():stack[-1][k]+=(v*num)\n",
    "            else:\n",
    "                atom=get_atom()\n",
    "                num=get_num()\n",
    "                stack[-1][atom]+=num\n",
    "        \n",
    "        # return ''.join(k+str(v)if v>1 else '' for k,v in sorted(stack[-1].items()))\n",
    "        return ''.join(k+(str(v)if v>1 else '') for k,v in sorted(stack[-1].items()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:  \n",
    "        n = len(formula)\n",
    "        stack = [collections.Counter()]    \n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if formula[i] == '(':\n",
    "                stack.append(collections.Counter())\n",
    "                i += 1\n",
    "            elif formula[i] == ')':\n",
    "                i += 1\n",
    "                curr_dict = stack.pop(-1)\n",
    "                start = i\n",
    "                # get the counter\n",
    "                while i < n and formula[i].isdigit():\n",
    "                    i += 1\n",
    "                multiplier = int(formula[start:i]) if formula[start:i] else 1\n",
    "                for a in curr_dict:\n",
    "                    stack[-1][a] = curr_dict[a] * multiplier + stack[-1][a]\n",
    "            else:\n",
    "                atom = formula[i]\n",
    "                if i + 1 < n and formula[i + 1].islower():\n",
    "                    atom += formula[i + 1]\n",
    "                    start = i + 2\n",
    "                else:\n",
    "                    start = i + 1\n",
    "                i = start\n",
    "                while i < n and formula[i].isdigit():\n",
    "                    i += 1\n",
    "                multiplier = int(formula[start:i]) if formula[start:i] else 1\n",
    "                stack[-1][atom] = multiplier + stack[-1][atom]\n",
    "        ans = ''\n",
    "        counter = stack[-1]\n",
    "        for atom in sorted(counter):\n",
    "            ans += atom\n",
    "            ans += str(counter[atom]) if counter[atom] > 1 else ''\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        n = len(formula)\n",
    "        def getNextItem(leftPtr):\n",
    "            symbolR = leftPtr+1\n",
    "            while symbolR < n and formula[symbolR].isalpha() and formula[symbolR].islower():\n",
    "                symbolR+=1\n",
    "            symbol = formula[leftPtr:symbolR]\n",
    "            num, numR = getNum(symbolR)\n",
    "            return (symbol, num, numR)\n",
    "        def getNum(leftPtr):\n",
    "            numR = leftPtr\n",
    "            num = 1\n",
    "            while numR < n and formula[numR].isdigit():\n",
    "                numR+=1\n",
    "            if numR != leftPtr:\n",
    "                num = int(formula[leftPtr:numR])\n",
    "            return num, numR\n",
    "        def multiDict(d, f):\n",
    "            for k in d.keys():\n",
    "                d[k] = d[k]*f\n",
    "            return d\n",
    "        def getFormula(leftPtr):\n",
    "            ret = collections.defaultdict(int)\n",
    "            curPtr = leftPtr\n",
    "            while curPtr < n:\n",
    "                curC = formula[curPtr]\n",
    "                if curC == '(':\n",
    "                    newRet, newIndex = getFormula(curPtr+1)\n",
    "                    for k in newRet.keys():\n",
    "                        ret[k]+=newRet[k]\n",
    "                    curPtr = newIndex\n",
    "                elif curC == ')':\n",
    "                    num, numR = getNum(curPtr+1)\n",
    "                    ret = multiDict(ret, num)\n",
    "                    return ret, numR\n",
    "                else:\n",
    "                    symbol, num, numR = getNextItem(curPtr)\n",
    "                    ret[symbol]+=num\n",
    "                    curPtr = numR\n",
    "            return ret, curPtr\n",
    "        ret = getFormula(0)[0]\n",
    "        ans = \"\"\n",
    "        keys = list(ret.keys())\n",
    "        keys.sort()\n",
    "        for k in keys:\n",
    "            if ret[k] != 1:\n",
    "                ans = ans + k + str(ret[k])\n",
    "            else:\n",
    "                ans = ans + k\n",
    "        return ans\n",
    "\n",
    "\n",
    "        # resultMap = {}\n",
    "        # def getNum(startIndex):\n",
    "        #     quantity = 1\n",
    "        #     rightIndex = startIndex\n",
    "        #     # print(startIndex)\n",
    "        #     while rightIndex < n and formula[rightIndex].isdigit():\n",
    "        #         rightIndex+=1\n",
    "        #     if rightIndex == startIndex:\n",
    "        #         return (1, startIndex)\n",
    "        #     else:\n",
    "        #         quantity = int(formula[startIndex: rightIndex])\n",
    "\n",
    "        #     return (quantity, rightIndex)\n",
    "        #     getNextATOM(rightIndex, [], False)\n",
    "        # def getNextATOM(startIndex, parenStack):\n",
    "        #     # print(startIndex)\n",
    "        #     curr_stack_map = parenStack[-1]\n",
    "        #     if startIndex >= n: return\n",
    "        #     if formula[startIndex] == '(':\n",
    "        #         # print(1)\n",
    "        #         parenStack.append(dict([]))\n",
    "        #         getNextATOM(startIndex+1, parenStack)\n",
    "        #     elif formula[startIndex] == ')':\n",
    "        #         (quantity, next_index) = getNum(startIndex+1)\n",
    "        #         # print(quantity, next_index)\n",
    "        #         # print(startIndex, parenStack)\n",
    "        #         parenStack.pop()\n",
    "        #         new_stack_map = parenStack[-1]\n",
    "        #         for key in curr_stack_map.keys():\n",
    "        #             new_stack_map[key] = new_stack_map.get(key, 0) + curr_stack_map.get(key, 1)*quantity\n",
    "        #         # print(2)\n",
    "        #         getNextATOM(next_index, parenStack)\n",
    "        #     else:\n",
    "        #         right_ptr = startIndex+1\n",
    "        #         #use right ptr to find the end of current symbol,\n",
    "        #         while right_ptr < n and formula[right_ptr].isalpha() and formula[right_ptr].islower():\n",
    "        #             right_ptr+=1\n",
    "        #         atomSymbol = formula[startIndex:right_ptr]\n",
    "        #         (quantity, next_index) = getNum(right_ptr)\n",
    "        #         # print(quantity, next_index)\n",
    "        #         curr_stack_map[atomSymbol] = curr_stack_map.get(atomSymbol, 0)+quantity\n",
    "        #         # print(3)\n",
    "        #         getNextATOM(next_index, parenStack)\n",
    "        \n",
    "        # ret = [{}]\n",
    "        # getNextATOM(0, ret)\n",
    "        # # print(sorted(resultMap.keys()))\n",
    "        # ret_map = ret[-1]\n",
    "\n",
    "        # ans = []\n",
    "        # for key in sorted(ret_map.keys()):\n",
    "        #     # print(key)\n",
    "        #     ans.append(key)\n",
    "        #     addedNum = str(ret_map[key])\n",
    "        #     if addedNum == '1': addedNum = \"\"\n",
    "        #     ans.append(addedNum)\n",
    "        # return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        lower, count = '', ''\n",
    "        stack = [1]\n",
    "        dic = dict()\n",
    "        for i in formula[::-1]:\n",
    "            if '0'<=i<='9':\n",
    "                count = i + count\n",
    "            if 'a'<=i<='z':\n",
    "                lower = i + lower\n",
    "            if i == ')':\n",
    "                stack.append(stack[-1]*int(count or '1'))\n",
    "                count = ''\n",
    "            if i == '(':\n",
    "                stack.pop()\n",
    "            if 'A'<=i<='Z':\n",
    "                if i+lower not in dic:\n",
    "                    dic[i+lower] = stack[-1]*int(count or '1')\n",
    "                else:\n",
    "                    dic[i+lower] += stack[-1]*int(count or '1')\n",
    "                lower = ''\n",
    "                count = ''\n",
    "        res = ''\n",
    "        for k,v in (sorted(dic.items())):\n",
    "            if v == 1: \n",
    "                res += k\n",
    "            else: \n",
    "                res += k + str(v)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        from collections import defaultdict\n",
    "        def dfs(s):\n",
    "            ans = defaultdict(int)\n",
    "            if not s:\n",
    "                return ans\n",
    "            i = 0\n",
    "            while i < len(s):\n",
    "                if s[i].isupper():\n",
    "                    j = i + 1\n",
    "                    while j < len(s) and s[j].islower():\n",
    "                        j += 1\n",
    "                    name = s[i:j]\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t * 10 + int(s[j])\n",
    "                        j += 1\n",
    "                    ans[name] += max(1,t)\n",
    "                    i = j\n",
    "                else:\n",
    "                    j = i + 1\n",
    "                    cnt= 1\n",
    "                    while cnt:\n",
    "                        if s[j] == '(':\n",
    "                            cnt += 1\n",
    "                        if s[j] == ')':\n",
    "                            cnt -= 1\n",
    "                        j += 1\n",
    "                    nxt = dfs(s[i + 1:j - 1])\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t * 10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(t,1)\n",
    "                    for k,v in nxt.items():\n",
    "                        ans[k] += v*t\n",
    "                    i = j\n",
    "            return ans\n",
    "        res = dfs(formula)\n",
    "        ans = ''\n",
    "        for k,v in sorted(res.items()):\n",
    "            ans += k if v == 1 else k + str(v)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def handle_formula(formula, pos):\n",
    "    dic = defaultdict(int)\n",
    "\n",
    "    while pos < len(formula):\n",
    "        c = formula[pos]\n",
    "        if c == ')':\n",
    "            return pos, dic\n",
    "\n",
    "        if c == '(':\n",
    "            pos, dic1 = handle_formula(formula, pos+1)\n",
    "            assert formula[pos] == ')'\n",
    "            pos += 1\n",
    "\n",
    "            num, pos = handle_num(formula, pos)\n",
    "            for k, v in dic1.items():\n",
    "                dic[k] += v*num\n",
    "            continue\n",
    "\n",
    "        name, num, pos = handle_atom(formula, pos)\n",
    "        dic[name] += num\n",
    "\n",
    "    return pos, dic\n",
    "\n",
    "\n",
    "def handle_atom(formula, pos):\n",
    "    s = formula[pos]\n",
    "\n",
    "    pos += 1\n",
    "\n",
    "    while pos < len(formula):\n",
    "        c = formula[pos]\n",
    "        if c not in 'abcdefghijklmnopqrstuvwxyz':\n",
    "            break\n",
    "        pos += 1\n",
    "        s += c\n",
    "    num, pos = handle_num(formula, pos)\n",
    "\n",
    "    return s, num, pos\n",
    "\n",
    "\n",
    "def handle_num(formula, pos):\n",
    "    \n",
    "    if pos == len(formula):\n",
    "        return 1, pos\n",
    "    \n",
    "    x = formula[pos]\n",
    "    if x not in '123456789':\n",
    "        return 1, pos\n",
    "    \n",
    "    pos += 1\n",
    "    while pos < len(formula):\n",
    "        c = formula[pos]\n",
    "        if c not in '0123456789':\n",
    "            break\n",
    "        pos += 1\n",
    "        x += c    \n",
    "            \n",
    "    return int(x), pos\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        lst = sorted(dic.keys())\n",
    "        res = ''\n",
    "        for s in lst:\n",
    "            num = dic[s]\n",
    "            res += '%s%s' % (s, str(num) if num > 1 else '')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "\n",
    "        def dfs(s):\n",
    "            if not s:\n",
    "                return {}\n",
    "            ans = defaultdict(int)\n",
    "            i = 0\n",
    "            while i < len(s):\n",
    "                if s[i].isupper(): # 大写字母\n",
    "                    j = i + 1\n",
    "                    # 小写字母\n",
    "                    while j < len(s) and s[j].islower():\n",
    "                        j += 1\n",
    "                    name = s[i:j]\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t*10 + int(s[j])\n",
    "                        j += 1\n",
    "                    ans[name] += max(1,t)\n",
    "                    i = j\n",
    "                elif s[i] == '(':\n",
    "                    cnt = 1\n",
    "                    j = i + 1\n",
    "                    while cnt:\n",
    "                        if s[j] == '(':\n",
    "                            cnt += 1\n",
    "                        if s[j] == ')':\n",
    "                            cnt -= 1\n",
    "                        j += 1\n",
    "                    cnts = dfs(s[i + 1:j-1])\n",
    "                    \n",
    "                    # 括号后数字\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t * 10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(t,1)\n",
    "                    for k,v in cnts.items():\n",
    "                        ans[k] += v*t\n",
    "                    i = j\n",
    "            return ans\n",
    "        a = list(dfs(formula).items())\n",
    "        a.sort()\n",
    "        ans = ''\n",
    "        for k,v in a:\n",
    "            if v > 1:\n",
    "                ans += k + str(v)\n",
    "            else:\n",
    "                ans += k\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stk = []\n",
    "        i = 0\n",
    "        n = len(formula)\n",
    "        dic = collections.Counter()\n",
    "        tmp_dict_list = []\n",
    "        s = ''\n",
    "        while i<n:\n",
    "            if not stk:\n",
    "                tmp_dict_list = []\n",
    "                if formula[i]=='(':\n",
    "                    stk.append('(')\n",
    "                    tmp_dict_list.append(collections.Counter())\n",
    "                    i+=1\n",
    "                elif formula[i].isupper():\n",
    "                    if s:\n",
    "                        dic[s]+=1\n",
    "                    s = formula[i]\n",
    "                    i+=1\n",
    "                    while i<n and formula[i].islower():\n",
    "                        s = s+formula[i]\n",
    "                        i+=1\n",
    "                    if i==n or (not formula[i].isdigit()):\n",
    "                        dic[s]+=1\n",
    "                        s=''\n",
    "                    elif formula[i].isdigit():\n",
    "                        num = 0\n",
    "                        while i<n and formula[i].isdigit():\n",
    "                            num = 10*num+int(formula[i])\n",
    "                            i+=1\n",
    "                        dic[s]+=num\n",
    "                        s = ''\n",
    "            else:\n",
    "                if formula[i]=='(':\n",
    "                    stk.append('(')\n",
    "                    tmp_dict_list.append(collections.Counter())\n",
    "                    i+=1\n",
    "                elif formula[i]==')':\n",
    "                    stk.pop()\n",
    "                    i+=1\n",
    "                    num = 0\n",
    "                    while i<n and formula[i].isdigit():\n",
    "                        num = 10*num+int(formula[i])\n",
    "                        i+=1\n",
    "                    if num==0:\n",
    "                        num=1\n",
    "                    tmp_dict = tmp_dict_list.pop()\n",
    "                    if tmp_dict_list:\n",
    "                        for k,v in tmp_dict.items():\n",
    "                            tmp_dict_list[-1][k]+=v*num\n",
    "                    else:\n",
    "                        for k,v in tmp_dict.items():\n",
    "                            dic[k]+=v*num\n",
    "\n",
    "                elif formula[i].isupper():\n",
    "                    if s:\n",
    "                        tmp_dict_list[-1][s]+=1\n",
    "                    s = formula[i]\n",
    "                    i+=1\n",
    "                    while i<n and formula[i].islower():\n",
    "                        s = s+formula[i]\n",
    "                        i+=1\n",
    "                    if i==n or (not formula[i].isdigit()):\n",
    "                        tmp_dict_list[-1][s]+=1\n",
    "                        s = ''\n",
    "                    elif formula[i].isdigit():\n",
    "                        num = 0\n",
    "                        while i<n and formula[i].isdigit():\n",
    "                            num = 10*num+int(formula[i])\n",
    "                            i+=1\n",
    "                        tmp_dict_list[-1][s]+=num\n",
    "                        s = ''\n",
    "\n",
    "        res = ''\n",
    "        for k in sorted(dic.keys()):\n",
    "            res=res+k\n",
    "            if dic[k]>1:\n",
    "                res+=str(dic[k])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    ch = formula[pose]\n",
    "    assert ch.isupper()\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #有小写\n",
    "    while  i<len(formula) and formula[i].islower():\n",
    "        i+=1\n",
    "    element = formula[pose:i]\n",
    "    #有数字\n",
    "    start_num = i\n",
    "    while i<len(formula) and formula[i].isdigit():\n",
    "        i += 1\n",
    "        flag = True\n",
    "    if flag:\n",
    "        if element not in dic:\n",
    "            dic[element] = int(formula[start_num:i])\n",
    "        else:\n",
    "            dic[element] += int(formula[start_num:i])\n",
    "    else:\n",
    "        if element not in dic:\n",
    "            dic[element] = 1\n",
    "        else:\n",
    "            dic[element] += 1\n",
    "    return i\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose, dic\n",
    "\n",
    "        ch = formula[pose]\n",
    "        if ch == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            assert formula[pose] == ')'\n",
    "            pose+=1\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose += 1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose, dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        assert pos == len(formula)\n",
    "        lst = sorted(dic.items(), key=lambda x: x[0])\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def handle_formula(formula, pos):\n",
    "    dic = {}\n",
    "    while pos < len(formula):\n",
    "        if formula[pos] == ')':#遇到右括号\n",
    "            return pos + 1, dic#位置加1，返回括号\n",
    "        x = formula[pos]\n",
    "        if x == '(':#遇到左括号\n",
    "            pos, dic1 = handle_formula(formula, pos+1)\n",
    "            num, pos = handle_num(formula, pos)\n",
    "            for v in dic1.keys():\n",
    "                if num == 0:\n",
    "                    continue\n",
    "                dic1[v] *= num\n",
    "            add_to_dic(dic, dic1)\n",
    "        else:\n",
    "            pos = handle_atom(formula, pos, dic)\n",
    "    # 检查是否有数量为0的元素，如果有，从字典中删除它们\n",
    "    for key in list(dic.keys()):\n",
    "        if dic[key] == 0:\n",
    "            dic[key] = 1\n",
    "    return pos, dic\n",
    "\n",
    "\n",
    "    return pos, dic\n",
    "\n",
    "def add_to_dic(dic, dic1):\n",
    "    for v in dic1.keys():\n",
    "        num = dic.get(v, 0)\n",
    "        # print(num)\n",
    "        num += dic1[v]\n",
    "        dic[v] = num\n",
    "\n",
    "def handle_atom(formula, pos, dic):\n",
    "    x = formula[pos]\n",
    "    assert x.isupper()\n",
    "    savpos = pos\n",
    "    pos += 1\n",
    "    while pos < len(formula) and formula[pos].islower():\n",
    "        pos += 1\n",
    "    element = formula[savpos:pos]\n",
    "    # print(element)\n",
    "    if pos < len(formula) and formula[pos].isdigit():\n",
    "        num, pos = handle_num(formula, pos)\n",
    "    else:\n",
    "        num = 1\n",
    "\n",
    "    dic[element] =dic.get(element,0) +num\n",
    "    # print(dic)\n",
    "    return pos\n",
    "\n",
    "def handle_num(formula, pos):\n",
    "    num = 0\n",
    "    while pos < len(formula) and formula[pos].isdigit():#检查边界并且检查当且字符是否是数字\n",
    "        print(int(formula[pos]))\n",
    "        num = num*10 + int(formula[pos])\n",
    "        pos += 1\n",
    "    return num, pos\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        assert pos == len(formula)\n",
    "\n",
    "\n",
    "        # print(dic)\n",
    "        lst = list(dic.keys())\n",
    "        lst.sort()\n",
    "\n",
    "        res = ''\n",
    "        for s in lst:\n",
    "            num = dic[s]\n",
    "            if num == 1:\n",
    "                res += s\n",
    "            else:\n",
    "                res += f\"{s}{num}\"\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        i = n-1\n",
    "\n",
    "        stack = [1]\n",
    "\n",
    "        lower = \"\"\n",
    "        count = \"\"\n",
    "        hmap = defaultdict(int)\n",
    "\n",
    "        while i > -1:\n",
    "            if 'a' <= s[i] <= 'z':\n",
    "                lower = s[i] + lower\n",
    "            elif '0' <= s[i] <= '9':\n",
    "                count = s[i] + count\n",
    "            elif 'A' <= s[i] <= 'Z':\n",
    "                hmap[s[i] + lower] += stack[-1] * int(count or '1')\n",
    "                lower = ''\n",
    "                count = ''\n",
    "            elif s[i] == ')':\n",
    "                stack.append(stack[-1] * int(count or '1'))\n",
    "                count = ''\n",
    "            elif s[i] == '(':\n",
    "                stack.pop() \n",
    "            \n",
    "            i -= 1\n",
    "\n",
    "        ans = ''\n",
    "        for k ,v in sorted(hmap.items()):\n",
    "            ans += k\n",
    "            if v > 1:\n",
    "                ans += str(v)\n",
    "            \n",
    "        return ans\n",
    "        \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    x = formula[pose]\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #大写\n",
    "    if x.isupper():\n",
    "        #有小写\n",
    "        while i<len(formula) and formula[i].islower():\n",
    "            i+=1\n",
    "        element = formula[pose:i]\n",
    "        #有数字\n",
    "        start_num = i\n",
    "        while i<len(formula) and formula[i].isdigit():\n",
    "            i+=1\n",
    "            flag = True\n",
    "        if flag:\n",
    "            if element not in dic:\n",
    "                dic[element] = int(formula[start_num:i])\n",
    "            else:\n",
    "                dic[element] += int(formula[start_num:i])\n",
    "        else:\n",
    "            if element not in dic:\n",
    "                dic[element] = 1\n",
    "            else:\n",
    "                dic[element] += 1\n",
    "    return i\n",
    "\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose + 1, dic\n",
    "\n",
    "        x = formula[pose]\n",
    "        if x == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose+=1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose,dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0 )\n",
    "\n",
    "        lst = sorted(dic.items(), key=lambda x: x[0])\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stk = []\n",
    "        i = 0\n",
    "        n = len(formula)\n",
    "        dic = collections.Counter()\n",
    "        tmp_dict_list = []\n",
    "        s = ''\n",
    "        while i<n:\n",
    "            if not stk:\n",
    "                tmp_dict_list = []\n",
    "                if formula[i]=='(':\n",
    "                    stk.append('(')\n",
    "                    tmp_dict_list.append(collections.Counter())\n",
    "                    i+=1\n",
    "                elif formula[i].isupper():\n",
    "                    if s:\n",
    "                        dic[s]+=1\n",
    "                    s = formula[i]\n",
    "                    i+=1\n",
    "                    while i<n and formula[i].islower():\n",
    "                        s = s+formula[i]\n",
    "                        i+=1\n",
    "                    if i==n or (not formula[i].isdigit()):\n",
    "                        dic[s]+=1\n",
    "                        s=''\n",
    "                else:\n",
    "                    num = 0\n",
    "                    while i<n and formula[i].isdigit():\n",
    "                        num = 10*num+int(formula[i])\n",
    "                        i+=1\n",
    "                    if num==0:\n",
    "                        num=1\n",
    "                    dic[s]+=num\n",
    "                    s = ''\n",
    "            else:\n",
    "                if formula[i]=='(':\n",
    "                    stk.append('(')\n",
    "                    tmp_dict_list.append(collections.Counter())\n",
    "                    i+=1\n",
    "                elif formula[i]==')':\n",
    "                    stk.pop()\n",
    "                    i+=1\n",
    "                    num = 0\n",
    "                    while i<n and formula[i].isdigit():\n",
    "                        num = 10*num+int(formula[i])\n",
    "                        i+=1\n",
    "                    if num==0:\n",
    "                        num=1\n",
    "                    tmp_dict = tmp_dict_list.pop()\n",
    "                    if tmp_dict_list:\n",
    "                        for k,v in tmp_dict.items():\n",
    "                            tmp_dict_list[-1][k]+=v*num\n",
    "                    else:\n",
    "                        for k,v in tmp_dict.items():\n",
    "                            dic[k]+=v*num\n",
    "\n",
    "                elif formula[i].isupper():\n",
    "                    if s:\n",
    "                        tmp_dict_list[-1][s]+=1\n",
    "                    s = formula[i]\n",
    "                    i+=1\n",
    "                    while i<n and formula[i].islower():\n",
    "                        s = s+formula[i]\n",
    "                        i+=1\n",
    "                    if i==n or (not formula[i].isdigit()):\n",
    "                        tmp_dict_list[-1][s]+=1\n",
    "                        s = ''\n",
    "                else:\n",
    "                    num = 0\n",
    "                    while i<n and formula[i].isdigit():\n",
    "                        num = 10*num+int(formula[i])\n",
    "                        i+=1\n",
    "                    tmp_dict_list[-1][s]+=num\n",
    "                    s = ''\n",
    "        res = ''\n",
    "        for k in sorted(dic.keys()):\n",
    "            res=res+k\n",
    "            if dic[k]>1:\n",
    "                res+=str(dic[k])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        # 数字先行，然后看跟的是元素还是括号\n",
    "        # 如果数字跟的是括号，则需要把一直到左括号的元素pop出来，次数乘数字\n",
    "        # 去掉左括号后，再把元素push回去，以防之后还有）\n",
    "        \n",
    "        # stack里面维护的是元素和括号的位置\n",
    "        # map里面放的是每个元素的次数\n",
    "        # 为了避免元素重复出现使得乘除的时候出现错误，每个元素多加了id suffix (比较新奇)\n",
    "        n = len(formula)\n",
    "        map = defaultdict(lambda: 1)\n",
    "        d = deque([])\n",
    "        i = idx = 0\n",
    "        while i < n:\n",
    "            c = formula[i]\n",
    "            if c == '(' or c == ')':\n",
    "                d.append(c)\n",
    "                i += 1\n",
    "            else:\n",
    "                if str.isdigit(c):\n",
    "                    # 获取完整的数字，并解析出对应的数值\n",
    "                    j = i\n",
    "                    while j < n and str.isdigit(formula[j]):\n",
    "                        j += 1\n",
    "                    cnt = int(formula[i:j])\n",
    "                    i = j\n",
    "                    # 如果栈顶元素是 )，说明当前数值可以应用给「连续一段」的原子中\n",
    "                    if d and d[-1] == ')':\n",
    "                        tmp = []\n",
    "                        d.pop()\n",
    "                        while d and d[-1] != '(':\n",
    "                            cur = d.pop()\n",
    "                            map[cur] *= cnt\n",
    "                            tmp.append(cur)\n",
    "                        d.pop() # pop (\n",
    "\n",
    "                        for k in range(len(tmp) - 1, -1, -1):\n",
    "                            d.append(tmp[k]) # 又把元素append回去\n",
    "                    # 如果栈顶元素不是 )，说明当前数值只能应用给栈顶的原子\n",
    "                    else:\n",
    "                        cur = d.pop()\n",
    "                        map[cur] *= cnt\n",
    "                        d.append(cur)\n",
    "                else:\n",
    "                    # 获取完整的原子名\n",
    "                    j = i + 1\n",
    "                    while j < n and str.islower(formula[j]):\n",
    "                        j += 1\n",
    "                    cur = formula[i:j] + \"_\" + str(idx)\n",
    "                    idx += 1 # 新的元素新的idx，再push到stack\n",
    "                    map[cur] = 1\n",
    "                    i = j\n",
    "                    d.append(cur)\n",
    "\n",
    "        #  将不同编号的相同原子进行合并\n",
    "        mm = defaultdict(int)\n",
    "        for key, cnt in map.items():\n",
    "            atom = key.split(\"_\")[0]\n",
    "            mm[atom] += cnt\n",
    "\n",
    "        # 对mm中的key进行排序作为答案\n",
    "        ans = []\n",
    "        for key in sorted(mm.keys()):\n",
    "            if mm[key] > 1:\n",
    "                ans.append(key+str(mm[key]))\n",
    "            else:\n",
    "                ans.append(key)\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        def getElement(index):\n",
    "            ele = formula[index]\n",
    "            while index+1 < len(formula) and formula[index+1].islower():\n",
    "                ele += formula[index+1]\n",
    "                index += 1\n",
    "            return ele\n",
    "        def getNum(index):\n",
    "            num = \"\"\n",
    "            while index < len(formula) and formula[index].isdigit():\n",
    "                num += formula[index]\n",
    "                index += 1\n",
    "            return num\n",
    "        inBrace = False\n",
    "        i = 0\n",
    "        map1 = collections.defaultdict(int)\n",
    "        recordStr = \"\"\n",
    "        theQueue = collections.deque()\n",
    "        theQueue.append(map1)\n",
    "        while i < len(formula):\n",
    "            ch = formula[i]\n",
    "            if ch.isalpha():\n",
    "                num = 1\n",
    "                ele = getElement(i)\n",
    "                #print(ele)\n",
    "                i += len(ele)\n",
    "                if i < len(formula) and formula[i].isdigit():\n",
    "                    num = getNum(i)\n",
    "                    i += len(num)\n",
    "                    num = int(num)\n",
    "                    #print(num)\n",
    "                theQueue[-1][ele] += num\n",
    "            else:\n",
    "                if ch == \")\":\n",
    "                    curMap = theQueue.pop()\n",
    "                    num = 1\n",
    "                    if i+1 < len(formula) and formula[i+1].isdigit():\n",
    "                        num = getNum(i+1)\n",
    "                        i += 1 + len(num)\n",
    "                        num = int(num)\n",
    "                    else:\n",
    "                        i += 1\n",
    "                    for key, value in curMap.items():\n",
    "                        theQueue[-1][key] += value * num\n",
    "                elif ch == \"(\":\n",
    "                    curMap = collections.defaultdict(int)\n",
    "                    theQueue.append(curMap)\n",
    "                    i += 1\n",
    "        recordStr = \"\"\n",
    "        for key in sorted(theQueue[-1]):\n",
    "            recordStr += key\n",
    "            if theQueue[-1][key] == 1:\n",
    "                continue\n",
    "            recordStr += str(theQueue[-1][key])\n",
    "        return recordStr\n",
    "\n",
    "\n",
    "                        \n",
    "                    \n",
    "\n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 大小写要区分，大写是新的开始，小写则是伴随\n",
    "    # 大写字母和 '(' 意味着新的统计量出现，即前面的该加入了\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        where = 0\n",
    "        mp = self.decode(formula, 0)\n",
    "        return self.printOut(mp)\n",
    "    \n",
    "    def decode(self, s: str, i: int) -> dict:\n",
    "        ans = dict()   # 总表\n",
    "        pre = dict()  # 之前收集到的有序表\n",
    "        name = \"\"     # 收集到的元素字母\n",
    "        cnt = 0\n",
    "        while i < len(s) and s[i] != ')':\n",
    "            if s[i].isupper() or s[i] == '(':  # 遇到了大写字母或左括号\n",
    "                self.push(ans, pre, name, cnt)\n",
    "                # 清空\n",
    "                name = \"\"\n",
    "                pre.clear()\n",
    "                cnt = 0\n",
    "                # 判断当前s[i]\n",
    "                if s[i].isalpha():\n",
    "                    name += s[i]\n",
    "                    i += 1\n",
    "                else:  # 左括号进入下一个嵌套\n",
    "                    pre = self.decode(s, i + 1)\n",
    "                    i = self.where + 1\n",
    "            elif s[i].isdigit():\n",
    "                cnt = cnt * 10 + int(s[i])\n",
    "                i += 1\n",
    "            else:  # 小写字母，前面一定跟着大写字母\n",
    "                name += s[i]\n",
    "                i += 1\n",
    "        self.push(ans, pre, name, cnt)   # 最后遍历完后结算，将最后的部分加入\n",
    "        self.where = i  # 更新位置\n",
    "        return ans\n",
    "    \n",
    "    # 加入总表\n",
    "    def push(self, ans: dict, mp: dict, name: str, cnt: int) -> None:\n",
    "        if len(name) > 0 or mp:\n",
    "            cnt = 1 if cnt == 0 else cnt   # 对于0其实对应的就是1\n",
    "            if len(name) > 0:\n",
    "                if name in ans.keys():\n",
    "                    ans[name] += cnt\n",
    "                else:\n",
    "                    ans[name] = cnt\n",
    "            else:  # 将 pre 加入总表\n",
    "                for k, v in mp.items():\n",
    "                    if k in ans.keys():\n",
    "                        ans[k] += v * cnt\n",
    "                    else:\n",
    "                        ans[k] = v * cnt\n",
    "    \n",
    "    # dict()按照字典序输出\n",
    "    def printOut(self, ans: dict) -> str:\n",
    "        lst = sorted(list(ans.keys()))\n",
    "        print(lst)\n",
    "        path = \"\"\n",
    "        for l in lst:\n",
    "            path += l\n",
    "            if ans[l] > 1:\n",
    "                path += str(ans[l])\n",
    "        return path\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, s: str) -> str:\n",
    "        stack = [1]\n",
    "        i = len(s) - 1\n",
    "        dic = collections.defaultdict(int)\n",
    "        lower = count = ''\n",
    "        while i > -1:\n",
    "            if '0' <= s[i] <= '9':\n",
    "                count = s[i] + count\n",
    "            elif 'a' <= s[i] <= 'z':\n",
    "                lower = s[i] + lower\n",
    "            elif s[i] == ')':\n",
    "                stack.append(stack[-1] * int(count or '1'))\n",
    "                count = ''\n",
    "            elif s[i] == '(':\n",
    "                stack.pop()\n",
    "            elif 'A' <= s[i] <= 'Z':\n",
    "                dic[s[i] + lower] += stack[-1] * int(count or '1')\n",
    "                count = ''\n",
    "                lower = ''\n",
    "            i -= 1\n",
    "        ans = ''\n",
    "        for k, v in sorted(dic.items()):\n",
    "            if v == 1:\n",
    "                ans += k\n",
    "            else:\n",
    "                ans += k + str(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stk = []\n",
    "        i = 0\n",
    "        n = len(formula)\n",
    "        dic = collections.Counter()\n",
    "        tmp_dict_list = []\n",
    "        s = ''\n",
    "        while i<n:\n",
    "            if not stk:\n",
    "                tmp_dict_list = []\n",
    "                if formula[i]=='(':\n",
    "                    stk.append('(')\n",
    "                    tmp_dict_list.append(collections.Counter())\n",
    "                    i+=1\n",
    "                elif formula[i].isupper():\n",
    "                    if s:\n",
    "                        dic[s]+=1\n",
    "                    s = formula[i]\n",
    "                    i+=1\n",
    "                    while i<n and formula[i].islower():\n",
    "                        s = s+formula[i]\n",
    "                        i+=1\n",
    "                    if i==n or (not formula[i].isdigit()):\n",
    "                        dic[s]+=1\n",
    "                        s=''\n",
    "                    elif formula[i].isdigit():\n",
    "                        num = 0\n",
    "                        while i<n and formula[i].isdigit():\n",
    "                            num = 10*num+int(formula[i])\n",
    "                            i+=1\n",
    "                        dic[s]+=num\n",
    "                        s = ''\n",
    "            else:\n",
    "                if formula[i]=='(':\n",
    "                    stk.append('(')\n",
    "                    tmp_dict_list.append(collections.Counter())\n",
    "                    i+=1\n",
    "                elif formula[i]==')':\n",
    "                    stk.pop()\n",
    "                    i+=1\n",
    "                    num = 0\n",
    "                    while i<n and formula[i].isdigit():\n",
    "                        num = 10*num+int(formula[i])\n",
    "                        i+=1\n",
    "                    if num==0:\n",
    "                        num=1\n",
    "                    tmp_dict = tmp_dict_list.pop()\n",
    "                    if tmp_dict_list:\n",
    "                        for k,v in tmp_dict.items():\n",
    "                            tmp_dict_list[-1][k]+=v*num\n",
    "                    else:\n",
    "                        for k,v in tmp_dict.items():\n",
    "                            dic[k]+=v*num\n",
    "\n",
    "                elif formula[i].isupper():\n",
    "                    if s:\n",
    "                        tmp_dict_list[-1][s]+=1\n",
    "                    s = formula[i]\n",
    "                    i+=1\n",
    "                    while i<n and formula[i].islower():\n",
    "                        s = s+formula[i]\n",
    "                        i+=1\n",
    "                    if i==n or (not formula[i].isdigit()):\n",
    "                        tmp_dict_list[-1][s]+=1\n",
    "                        s = ''\n",
    "                    elif formula[i].isdigit():\n",
    "                        num = 0\n",
    "                        while i<n and formula[i].isdigit():\n",
    "                            num = 10*num+int(formula[i])\n",
    "                            i+=1\n",
    "                        tmp_dict_list[-1][s]+=num\n",
    "                        s = ''\n",
    "\n",
    "        res = ''\n",
    "        for k in sorted(dic.keys()):\n",
    "            res=res+k\n",
    "            if dic[k]>1:\n",
    "                res+=str(dic[k])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        a, _ = self.f(formula, 0)\n",
    "        ans = []\n",
    "        for x in a.keys():\n",
    "            ans.append(x + str(a[x])) if a[x] > 1 else ans.append(x)\n",
    "        return ''.join(sorted(ans))\n",
    "        \n",
    "    def f(self, formula, i):\n",
    "        d = {}\n",
    "        cur = None\n",
    "        while i < len(formula):\n",
    "            if formula[i] == '(':\n",
    "                if isinstance(cur, str):\n",
    "                    self.dict_add(d, cur, 1)\n",
    "                elif isinstance(cur, dict):\n",
    "                    for x in cur.keys():\n",
    "                        self.dict_add(d, x, cur[x])\n",
    "                cur, i = self.f(formula, i+1)\n",
    "                pre = None\n",
    "                num = 0\n",
    "            elif formula[i] == ')':\n",
    "                break\n",
    "            elif ord(formula[i]) <= ord('Z') and ord(formula[i]) >= ord('A'):\n",
    "                if isinstance(cur, str):\n",
    "                    self.dict_add(d, cur, 1)\n",
    "                elif isinstance(cur, dict):\n",
    "                    for x in cur.keys():\n",
    "                        self.dict_add(d, x, cur[x])\n",
    "                cur = formula[i]\n",
    "                pre = None\n",
    "                num = 0\n",
    "            elif ord(formula[i]) <= ord('z') and ord(formula[i]) >= ord('a'):\n",
    "                cur += formula[i]\n",
    "                pre = None\n",
    "                num = 0\n",
    "            else:\n",
    "                if num != 0:\n",
    "                    if isinstance(pre, dict):\n",
    "                        prenum = num\n",
    "                        num = num*10 + int(formula[i])\n",
    "                        for x in pre.keys():\n",
    "                            self.dict_add(d, x, -pre[x]*prenum)\n",
    "                            self.dict_add(d, x, pre[x]*num)\n",
    "                    elif isinstance(pre, str):\n",
    "                        self.dict_add(d, pre, -num)\n",
    "                        num = num*10 + int(formula[i])\n",
    "                        self.dict_add(d, pre, num)\n",
    "                else:\n",
    "                    if isinstance(cur, dict):\n",
    "                        for x in cur.keys():\n",
    "                            self.dict_add(d, x, cur[x]*int(formula[i]))\n",
    "                    elif isinstance(cur, str):\n",
    "                        self.dict_add(d, cur, int(formula[i]))\n",
    "                    pre = cur\n",
    "                    num = int(formula[i])\n",
    "                    cur = None\n",
    "            i += 1\n",
    "        if isinstance(cur, str):\n",
    "            self.dict_add(d, cur, 1)\n",
    "        elif isinstance(cur, dict):\n",
    "            for x in cur.keys():\n",
    "                self.dict_add(d, x, cur[x])\n",
    "        return d, i\n",
    "    \n",
    "    def dict_add(self, d, var, n):\n",
    "        if var in d.keys():\n",
    "            d[var] += n\n",
    "        else:\n",
    "            d[var] = n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    ch = formula[pose]\n",
    "    assert ch.isupper()\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #有小写\n",
    "    while  i<len(formula) and formula[i].islower():\n",
    "        i+=1\n",
    "    element = formula[pose:i]\n",
    "    #有数字\n",
    "    start_num = i\n",
    "    while i<len(formula) and formula[i].isdigit():\n",
    "        i += 1\n",
    "        flag = True\n",
    "    if flag:\n",
    "        if element not in dic:\n",
    "            dic[element] = int(formula[start_num:i])\n",
    "        else:\n",
    "            dic[element] += int(formula[start_num:i])\n",
    "    else:\n",
    "        if element not in dic:\n",
    "            dic[element] = 1\n",
    "        else:\n",
    "            dic[element] += 1\n",
    "    return i\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose, dic\n",
    "\n",
    "        ch = formula[pose]\n",
    "        if ch == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            assert formula[pose] == ')'\n",
    "            pose+=1\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose += 1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose, dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        assert pos == len(formula)\n",
    "        lst = sorted(dic.items(), key=lambda x: x[0])\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        ans = self.countOfAtomsOutputDict(formula)\n",
    "        keys_sorted = sorted(ans.keys())\n",
    "        ans_str = \"\"\n",
    "        for i in keys_sorted:\n",
    "            if ans[i] == 1:\n",
    "                ans_str += i\n",
    "            else:\n",
    "                ans_str += (i + str(ans[i]))\n",
    "        \n",
    "        return ans_str\n",
    "    def submitData(self, data, atomName, atomCount):\n",
    "        if atomName not in data:\n",
    "            data[atomName] = 0\n",
    "        data[atomName] += atomCount\n",
    "\n",
    "    def countOfAtomsOutputDict(self, formula: str) -> Tuple[int, Dict[str, int]]:\n",
    "        dataStk = [{}]\n",
    "\n",
    "        atomName = \"\"\n",
    "        atomCount = 0\n",
    "        i = 0\n",
    "        while i < len(formula):\n",
    "            if formula[i] == '(':\n",
    "                if formula[i-1].isdigit():\n",
    "                    self.submitData(dataStk[-1], atomName, atomCount)\n",
    "                else:\n",
    "                    self.submitData(dataStk[-1], atomName, 1)\n",
    "\n",
    "                atomName = \"\"\n",
    "                atomCount = 0\n",
    "                dataStk.append({})\n",
    "                i += 1\n",
    "            elif formula[i] == ')':\n",
    "                if atomName != '':\n",
    "                    if formula[i-1].isdigit():\n",
    "                        self.submitData(dataStk[-1], atomName, atomCount)\n",
    "                    else:\n",
    "                        self.submitData(dataStk[-1], atomName, 1)\n",
    "                \n",
    "                i += 1\n",
    "                groupCount = 0\n",
    "                while i < len(formula) and formula[i].isdigit():\n",
    "                    groupCount = groupCount * 10 + int(formula[i])\n",
    "                    i += 1\n",
    "                if groupCount == 0:\n",
    "                    groupCount = 1\n",
    "\n",
    "                subData = dataStk.pop()\n",
    "                thisData = dataStk[-1]\n",
    "\n",
    "                for keyName in subData:\n",
    "                    if keyName not in thisData:\n",
    "                        thisData[keyName] = 0\n",
    "                    thisData[keyName] += subData[keyName] * groupCount\n",
    "                \n",
    "                atomName = \"\"\n",
    "                atomCount = 0\n",
    "            elif formula[i].isdigit():\n",
    "                if i >= 1:\n",
    "                    if formula[i-1].isdigit():\n",
    "                        atomCount = atomCount * 10 + int(formula[i])\n",
    "                    elif formula[i-1].islower() or formula[i-1].isupper():\n",
    "                        atomCount = int(formula[i])\n",
    "                i += 1\n",
    "            elif formula[i].isupper():\n",
    "                if i >= 1:\n",
    "                    if formula[i-1].isdigit():\n",
    "                        self.submitData(dataStk[-1], atomName, atomCount)\n",
    "                    elif formula[i-1].isupper():\n",
    "                        self.submitData(dataStk[-1], atomName, 1)\n",
    "                    elif formula[i-1].islower():\n",
    "                        self.submitData(dataStk[-1], atomName, 1)\n",
    "                \n",
    "                atomName = formula[i]\n",
    "                atomCount = 1\n",
    "                i += 1\n",
    "            elif formula[i].islower():\n",
    "                atomName += formula[i]\n",
    "                atomCount = 1\n",
    "                i += 1\n",
    "        \n",
    "        if atomName != '':\n",
    "            self.submitData(dataStk[-1], atomName, atomCount)\n",
    "        if '' in dataStk[-1]:\n",
    "            del dataStk[-1]['']\n",
    "        return dataStk.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        cnt=collections.Counter()\n",
    "\n",
    "        n=len(formula)\n",
    "        stack=[]\n",
    "        i=0\n",
    "        while i <=n:\n",
    "            \n",
    "            if i==n:\n",
    "                tmp=\"\"\n",
    "                k=\"\"\n",
    "                while stack:\n",
    "                    cur=stack.pop()\n",
    "                    if cur.islower():\n",
    "                        tmp=cur+tmp\n",
    "                    elif cur.isupper():\n",
    "                        tmp=cur+tmp\n",
    "                        if len(k)!=0:\n",
    "                            cnt[tmp]+=int(k)\n",
    "                        else:\n",
    "                            cnt[tmp]+=1\n",
    "                        k=\"\"\n",
    "                        tmp=\"\"\n",
    "                    elif cur.isdigit():\n",
    "                        k=cur+k\n",
    "            \n",
    "            elif formula[i]==\")\":\n",
    "                mark=i\n",
    "                \n",
    "                b=\"\"\n",
    "                while i+1<n and formula[i+1].isdigit():\n",
    "                    b+=formula[i+1]\n",
    "                    i=i+1\n",
    "                tmp=\"\"\n",
    "                k=\"\"\n",
    "        \n",
    "                while stack[-1]!=\"(\":\n",
    "                    cur=stack.pop()\n",
    "                    if cur.islower():\n",
    "                        tmp=cur+tmp\n",
    "                    elif cur.isupper():\n",
    "                        tmp=cur+tmp\n",
    "                        \n",
    "                        if len(k)!=0:\n",
    "                            cnt[tmp]+=int(k)\n",
    "                        else:\n",
    "                            cnt[tmp]+=1\n",
    "                        \n",
    "                        k=\"\"\n",
    "                        tmp=\"\"\n",
    "                    elif cur.isdigit():\n",
    "                        k=cur+k\n",
    "                if len(stack)>1:\n",
    "                    stack.pop()\n",
    "\n",
    "                if len(b)!=0:\n",
    "                    b=int(b)\n",
    "                    for x in cnt:\n",
    "                        cnt[x]=cnt[x]*b\n",
    "                for x in cnt:\n",
    "                    if cnt[x]==1:\n",
    "                        for k in x:\n",
    "                            stack.append(x)\n",
    "                    elif cnt[x]>=1:\n",
    "                        for k in x:\n",
    "                            stack.append(k)\n",
    "                        for k in str(cnt[x]):\n",
    "                            stack.append(k)\n",
    "                cnt=collections.Counter()\n",
    "            else:\n",
    "                stack.append(formula[i])\n",
    "           # print(cnt)\n",
    "           # print(stack)\n",
    "            i=i+1\n",
    "        arr=list(sorted(cnt.items()))\n",
    "        ans=\"\"\n",
    "       # print(arr)\n",
    "        for a in arr:\n",
    "            if a[1]==1:\n",
    "                ans+=a[0]\n",
    "            elif a[1]>1:\n",
    "                ans+=a[0]+str(a[1])\n",
    "        return ans\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "\n",
    "\n",
    "        def dfs(s):\n",
    "            if not s:\n",
    "                return {}\n",
    "            ans = defaultdict(int)\n",
    "            i = 0\n",
    "            while i < len(s):\n",
    "                if ord('A') <= ord(s[i]) <= ord('Z'):\n",
    "                    j = i + 1\n",
    "                    while j < len(s) and ord('a') <= ord(s[j]) <= ord('z'):\n",
    "                        j += 1\n",
    "                    name = s[i:j]\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t *10 + int(s[j])\n",
    "                        j += 1\n",
    "                    ans[name] += max(1,t)\n",
    "                    i = j\n",
    "                elif s[i] == '(':\n",
    "                    j = i + 1\n",
    "                    cnt = 1\n",
    "                    while j < len(s):\n",
    "                        if s[j] == '(':\n",
    "                            cnt += 1\n",
    "                        if s[j] == ')':\n",
    "                            cnt -= 1\n",
    "                            if cnt == 0:\n",
    "                                break\n",
    "                        j += 1\n",
    "                    nxt = dfs(s[i + 1:j])\n",
    "                    j += 1\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t*10+ int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(t,1)\n",
    "                    for k,v in nxt.items():\n",
    "                        ans[k] += v*t\n",
    "                    i = j\n",
    "            return ans\n",
    "        res = dfs(formula)\n",
    "        ans = ''\n",
    "        for k,v in sorted(res.items()):\n",
    "            ans +=  k if v == 1 else k+str(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    x = formula[pose]\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #大写\n",
    "    if x.isupper():\n",
    "        #有小写\n",
    "        while i<len(formula) and formula[i].islower():\n",
    "            i+=1\n",
    "        element = formula[pose:i]\n",
    "        #有数字\n",
    "        start_num = i\n",
    "        while i<len(formula) and formula[i].isdigit():\n",
    "            i+=1\n",
    "            flag = True\n",
    "        if flag:\n",
    "            if element not in dic:\n",
    "                dic[element] = int(formula[start_num:i])\n",
    "            else:\n",
    "                dic[element] += int(formula[start_num:i])\n",
    "        else:\n",
    "            if element not in dic:\n",
    "                dic[element] = 1\n",
    "            else:\n",
    "                dic[element] += 1\n",
    "    return i\n",
    "\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose + 1, dic\n",
    "\n",
    "        x = formula[pose]\n",
    "        if x == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose+=1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose,dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0 )\n",
    "\n",
    "        lst = sorted(dic.items(), key=lambda x: x[0])\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        self.where = 0\n",
    "        def dfs(i):\n",
    "            d = {}\n",
    "            while i < len(formula):\n",
    "                x = formula[i]\n",
    "                string = ''\n",
    "                if formula[i].isalpha():\n",
    "                    # if formula[i].isalpha()\n",
    "\n",
    "                    if i+1<len(formula):\n",
    "                        if formula[i+1].isdigit():\n",
    "                            end = i + 1\n",
    "                            while end < len(formula) and formula[end].isdigit():\n",
    "                                end += 1\n",
    "                            string = formula[i]\n",
    "                            num = int(formula[i+1:end])\n",
    "                            i = end\n",
    "                        else:\n",
    "                            if formula[i+1].islower():\n",
    "                                string = formula[i:i+2]\n",
    "                                if i+2 < len(formula) and formula[i+2].isdigit():\n",
    "                                    end = i + 2\n",
    "                                    while end < len(formula) and formula[end].isdigit():\n",
    "                                        end += 1\n",
    "                                    num = int(formula[i+2:end])\n",
    "                                    i = end\n",
    "                                else:\n",
    "                                    num = 1\n",
    "                                    i+=2\n",
    "                            else:\n",
    "                                string = formula[i:i+1]\n",
    "                                num = 1\n",
    "                                i+=1\n",
    "                    else:\n",
    "                        string = formula[i]\n",
    "                        num = 1\n",
    "                        i+=1\n",
    "\n",
    "                    if string in d:\n",
    "                        d[string]+= int(num)\n",
    "                    else:\n",
    "                        d[string]=int(num)\n",
    "\n",
    "                elif formula[i] == '(':\n",
    "                    dt,beishu = dfs(i+1)\n",
    "                    i = self.where\n",
    "                    for k in dt:\n",
    "                        if k in d:\n",
    "                            d[k] += dt[k]*beishu\n",
    "                        else:\n",
    "                            d[k] = dt[k]*beishu\n",
    "                else:\n",
    "                    if i + 1 < len(formula):\n",
    "                        \n",
    "                        if formula[i+1].isdigit():\n",
    "                            end = i +2\n",
    "                            while end < len(formula) and formula[end].isdigit():\n",
    "                                end += 1\n",
    "                            beishu = int(formula[i+1:end])\n",
    "                            self.where = end\n",
    "                        else:\n",
    "                            beishu =1\n",
    "                            self.where = i+1\n",
    "                    else:\n",
    "                        beishu =1\n",
    "                        self.where = i+1\n",
    "                    return d,beishu\n",
    "            return d,1\n",
    "        ans,_ = dfs(0)\n",
    "        string = sorted([k for k in ans.keys()])\n",
    "        anss = \"\"\n",
    "        for x in string:\n",
    "            if ans[x] == 1:\n",
    "                anss+= x \n",
    "            else:\n",
    "                anss+= x + str(ans[x])\n",
    "        return anss\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    x = formula[pose]\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #大写\n",
    "    if x.isupper():\n",
    "        #有小写\n",
    "        while i<len(formula) and formula[i].islower():\n",
    "            i+=1\n",
    "        element = formula[pose:i]\n",
    "        #有数字\n",
    "        start_num = i\n",
    "        while i<len(formula) and formula[i].isdigit():\n",
    "            i+=1\n",
    "            flag = True\n",
    "        if flag:\n",
    "            if element not in dic:\n",
    "                dic[element] = int(formula[start_num:i])\n",
    "            else:\n",
    "                dic[element] += int(formula[start_num:i])\n",
    "        else:\n",
    "            if element not in dic:\n",
    "                dic[element] = 1\n",
    "            else:\n",
    "                dic[element] += 1\n",
    "    return i\n",
    "\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose + 1, dic\n",
    "\n",
    "        x = formula[pose]\n",
    "        if x == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose+=1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose,dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0 )\n",
    "\n",
    "        lst = sorted(dic.items(), key=lambda x: x[0])\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stk = []\n",
    "        i = 0\n",
    "        n = len(formula)\n",
    "        dic = collections.Counter()\n",
    "        tmp_dict_list = []\n",
    "        s = ''\n",
    "        while i<n:\n",
    "            if not stk:\n",
    "                tmp_dict_list = []\n",
    "                if formula[i]=='(':\n",
    "                    stk.append('(')\n",
    "                    tmp_dict_list.append(collections.Counter())\n",
    "                    i+=1\n",
    "                elif formula[i].isupper():\n",
    "                    if s:\n",
    "                        dic[s]+=1\n",
    "                    s = formula[i]\n",
    "                    i+=1\n",
    "                    while i<n and formula[i].islower():\n",
    "                        s = s+formula[i]\n",
    "                        i+=1\n",
    "                    if i==n or (not formula[i].isdigit()):\n",
    "                        dic[s]+=1\n",
    "                        s=''\n",
    "                else:\n",
    "                    num = 0\n",
    "                    while i<n and formula[i].isdigit():\n",
    "                        num = 10*num+int(formula[i])\n",
    "                        i+=1\n",
    "                    if num==0:\n",
    "                        num=1\n",
    "                    dic[s]+=num\n",
    "                    s = ''\n",
    "            else:\n",
    "                if formula[i]=='(':\n",
    "                    stk.append('(')\n",
    "                    tmp_dict_list.append(collections.Counter())\n",
    "                    i+=1\n",
    "                elif formula[i]==')':\n",
    "                    stk.pop()\n",
    "                    i+=1\n",
    "                    num = 0\n",
    "                    while i<n and formula[i].isdigit():\n",
    "                        num = 10*num+int(formula[i])\n",
    "                        i+=1\n",
    "                    if num==0:\n",
    "                        num=1\n",
    "                    tmp_dict = tmp_dict_list.pop()\n",
    "                    if tmp_dict_list:\n",
    "                        for k,v in tmp_dict.items():\n",
    "                            tmp_dict_list[-1][k]+=v*num\n",
    "                    else:\n",
    "                        for k,v in tmp_dict.items():\n",
    "                            dic[k]+=v*num\n",
    "\n",
    "                elif formula[i].isupper():\n",
    "                    if s:\n",
    "                        tmp_dict_list[-1][s]+=1\n",
    "                    s = formula[i]\n",
    "                    i+=1\n",
    "                    while i<n and formula[i].islower():\n",
    "                        s = s+formula[i]\n",
    "                        i+=1\n",
    "                    if i==n or (not formula[i].isdigit()):\n",
    "                        tmp_dict_list[-1][s]+=1\n",
    "                        s = ''\n",
    "                else:\n",
    "                    num = 0\n",
    "                    while i<n and formula[i].isdigit():\n",
    "                        num = 10*num+int(formula[i])\n",
    "                        i+=1\n",
    "                    tmp_dict_list[-1][s]+=num\n",
    "                    s = ''\n",
    "        res = ''\n",
    "        for k in sorted(dic.keys()):\n",
    "            res=res+k\n",
    "            if dic[k]>1:\n",
    "                res+=str(dic[k])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stk = []\n",
    "        i = 0\n",
    "        n = len(formula)\n",
    "        dic = collections.Counter()\n",
    "        tmp_dict_list = []\n",
    "        s = ''\n",
    "        while i<n:\n",
    "            if not stk:\n",
    "                tmp_dict_list = []\n",
    "                if formula[i]=='(':\n",
    "                    stk.append('(')\n",
    "                    tmp_dict_list.append(collections.Counter())\n",
    "                    i+=1\n",
    "                elif formula[i].isupper():\n",
    "                    if s:\n",
    "                        dic[s]+=1\n",
    "                    s = formula[i]\n",
    "                    i+=1\n",
    "                    while i<n and formula[i].islower():\n",
    "                        s = s+formula[i]\n",
    "                        i+=1\n",
    "                    if i==n or (not formula[i].isdigit()):\n",
    "                        dic[s]+=1\n",
    "                        s=''\n",
    "                    elif formula[i].isdigit():\n",
    "                        num = 0\n",
    "                        while i<n and formula[i].isdigit():\n",
    "                            num = 10*num+int(formula[i])\n",
    "                            i+=1\n",
    "                        dic[s]+=num\n",
    "                        s = ''\n",
    "            else:\n",
    "                if formula[i]=='(':\n",
    "                    stk.append('(')\n",
    "                    tmp_dict_list.append(collections.Counter())\n",
    "                    i+=1\n",
    "                elif formula[i]==')':\n",
    "                    stk.pop()\n",
    "                    i+=1\n",
    "                    num = 0\n",
    "                    while i<n and formula[i].isdigit():\n",
    "                        num = 10*num+int(formula[i])\n",
    "                        i+=1\n",
    "                    if num==0:\n",
    "                        num=1\n",
    "                    tmp_dict = tmp_dict_list.pop()\n",
    "                    if tmp_dict_list:\n",
    "                        for k,v in tmp_dict.items():\n",
    "                            tmp_dict_list[-1][k]+=v*num\n",
    "                    else:\n",
    "                        for k,v in tmp_dict.items():\n",
    "                            dic[k]+=v*num\n",
    "\n",
    "                elif formula[i].isupper():\n",
    "                    if s:\n",
    "                        tmp_dict_list[-1][s]+=1\n",
    "                    s = formula[i]\n",
    "                    i+=1\n",
    "                    while i<n and formula[i].islower():\n",
    "                        s = s+formula[i]\n",
    "                        i+=1\n",
    "                    if i==n or (not formula[i].isdigit()):\n",
    "                        tmp_dict_list[-1][s]+=1\n",
    "                        s = ''\n",
    "                    elif formula[i].isdigit():\n",
    "                        num = 0\n",
    "                        while i<n and formula[i].isdigit():\n",
    "                            num = 10*num+int(formula[i])\n",
    "                            i+=1\n",
    "                        tmp_dict_list[-1][s]+=num\n",
    "                        s = ''\n",
    "\n",
    "        res = ''\n",
    "        for k in sorted(dic.keys()):\n",
    "            res=res+k\n",
    "            if dic[k]>1:\n",
    "                res+=str(dic[k])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    ch = formula[pose]\n",
    "    assert ch.isupper()\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #有小写\n",
    "    while  i<len(formula) and formula[i].islower():\n",
    "        i+=1\n",
    "    element = formula[pose:i]\n",
    "    #有数字\n",
    "    start_num = i\n",
    "    while i<len(formula) and formula[i].isdigit():\n",
    "        i += 1\n",
    "        flag = True\n",
    "    if flag:\n",
    "        if element not in dic:\n",
    "            dic[element] = int(formula[start_num:i])\n",
    "        else:\n",
    "            dic[element] += int(formula[start_num:i])\n",
    "    else:\n",
    "        if element not in dic:\n",
    "            dic[element] = 1\n",
    "        else:\n",
    "            dic[element] += 1\n",
    "    return i\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose, dic\n",
    "\n",
    "        ch = formula[pose]\n",
    "        if ch == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            assert formula[pose] == ')'\n",
    "            pose+=1\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose += 1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose, dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        assert pos == len(formula)\n",
    "        lst = sorted(dic.items())\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countOfAtoms(self, formula: str) -> str:\r\n",
    "        counter={}\r\n",
    "\r\n",
    "        L=len(formula)\r\n",
    "        # stack=[]\r\n",
    "        # cur=stack[-1]\r\n",
    "\r\n",
    "        idx=L-1\r\n",
    "        mul_stack=[1]\r\n",
    "        # cur_mul=1\r\n",
    "        num=1\r\n",
    "        while idx>=0:\r\n",
    "            if formula[idx]==')':\r\n",
    "                mul_stack.append(num*mul_stack[-1])\r\n",
    "                # cur_mul=mul_stack[-1]\r\n",
    "                num=1\r\n",
    "                idx-=1\r\n",
    "            elif formula[idx]=='(':\r\n",
    "                mul_stack.pop()\r\n",
    "                # cur_mul=mul_stack[-1]\r\n",
    "                idx-=1\r\n",
    "            elif formula[idx].isnumeric():\r\n",
    "                end=idx\r\n",
    "                while idx>=0 and formula[idx].isnumeric():\r\n",
    "                    idx-=1\r\n",
    "                start=idx+1\r\n",
    "                num=int(formula[start:end+1])\r\n",
    "            else:\r\n",
    "                end=idx\r\n",
    "\r\n",
    "                while idx>=0 and formula[idx].islower():\r\n",
    "                    idx-=1\r\n",
    "                start=idx\r\n",
    "                name=formula[start:end+1]\r\n",
    "                val=counter.get(name,0)+num*mul_stack[-1]\r\n",
    "                counter[name]=val\r\n",
    "                num=1\r\n",
    "                idx-=1\r\n",
    "        \r\n",
    "        ret=[]\r\n",
    "        for key in sorted(counter.keys()):\r\n",
    "            ret.append(str(key)+(str(counter[key]) if counter[key]>1 else ''))\r\n",
    "        return ''.join(ret)\r\n",
    "\r\n",
    "                \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stack = [1]\n",
    "        i = len(formula) - 1\n",
    "        dic = collections.defaultdict(int)\n",
    "        lower = count = ''\n",
    "        while i > -1:\n",
    "            if '0' <= formula[i] <= '9':\n",
    "                count = formula[i] + count\n",
    "            elif 'a' <= formula[i] <= 'z':\n",
    "                lower = formula[i] + lower\n",
    "            elif formula[i] == ')':\n",
    "                stack.append(stack[-1] * int(count or '1'))\n",
    "                count = ''\n",
    "            elif formula[i] == '(':\n",
    "                stack.pop()\n",
    "            elif 'A' <= formula[i] <= 'Z':\n",
    "                dic[formula[i] + lower] += stack[-1] * int(count or '1')\n",
    "                count = ''\n",
    "                lower = ''\n",
    "            i -= 1\n",
    "        ans = ''\n",
    "        for k, v in sorted(dic.items()):\n",
    "            if v == 1:\n",
    "                ans += k\n",
    "            else:\n",
    "                ans += k + str(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    ch = formula[pose]\n",
    "    assert ch.isupper()\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #有小写\n",
    "    while  i<len(formula) and formula[i].islower():\n",
    "        i+=1\n",
    "    element = formula[pose:i]\n",
    "    #有数字\n",
    "    start_num = i\n",
    "    while i<len(formula) and formula[i].isdigit():\n",
    "        i += 1\n",
    "        flag = True\n",
    "    if flag:\n",
    "        if element not in dic:\n",
    "            dic[element] = int(formula[start_num:i])\n",
    "        else:\n",
    "            dic[element] += int(formula[start_num:i])\n",
    "    else:\n",
    "        if element not in dic:\n",
    "            dic[element] = 1\n",
    "        else:\n",
    "            dic[element] += 1\n",
    "    return i\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose, dic\n",
    "\n",
    "        ch = formula[pose]\n",
    "        if ch == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            assert formula[pose] == ')'\n",
    "            pose+=1\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose += 1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose, dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        assert pos == len(formula)\n",
    "        lst = sorted(dic.items(), key=lambda x: x[0])\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        a, _ = self.f(formula, 0)\n",
    "        ans = []\n",
    "        for x in a.keys():\n",
    "            ans.append(x + str(a[x])) if a[x] > 1 else ans.append(x)\n",
    "        return ''.join(sorted(ans))\n",
    "        \n",
    "    def f(self, formula, i):\n",
    "        d = {}\n",
    "        cur = None\n",
    "        num = 0\n",
    "        while i < len(formula):\n",
    "            if formula[i] == '(':\n",
    "                d, cur, num = self.checkout(d, cur, num)\n",
    "                cur, i = self.f(formula, i+1)\n",
    "                num = 0\n",
    "            elif formula[i] == ')':\n",
    "                break\n",
    "            elif ord(formula[i]) <= ord('Z') and ord(formula[i]) >= ord('A'):\n",
    "                d, cur, num = self.checkout(d, cur, num)\n",
    "                cur = formula[i]\n",
    "            elif ord(formula[i]) <= ord('z') and ord(formula[i]) >= ord('a'):\n",
    "                cur += formula[i]\n",
    "            else:\n",
    "                num = num*10 + int(formula[i])\n",
    "            i += 1\n",
    "        d, cur, num = self.checkout(d, cur, num)\n",
    "        return d, i\n",
    "    \n",
    "    def checkout(self, d, cur, num):\n",
    "        if cur is not None:\n",
    "            num = 1 if num == 0 else num\n",
    "            if isinstance(cur, str):\n",
    "                self.dict_add(d, cur, num)\n",
    "            elif isinstance(cur, dict):\n",
    "                for x in cur.keys():\n",
    "                    self.dict_add(d, x, cur[x]*num)\n",
    "        cur = None\n",
    "        num = 0\n",
    "        return d, cur, num\n",
    "\n",
    "    def dict_add(self, d, var, n):\n",
    "        if var in d.keys():\n",
    "            d[var] += n\n",
    "        else:\n",
    "            d[var] = n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        def dfs():\n",
    "            nonlocal idx\n",
    "            atom, cnt = '', ''\n",
    "            res = collections.defaultdict(int)\n",
    "            while idx < len(formula):\n",
    "                cur = formula[idx]\n",
    "                idx += 1\n",
    "                if cur.isalpha():\n",
    "                    atom = cur + atom\n",
    "                    if cur.isupper():  # stop a new atom\n",
    "                        res[atom] += int(cnt) if cnt else 1\n",
    "                        atom, cnt = '', ''\n",
    "                if cur.isdigit():\n",
    "                    cnt = cur + cnt\n",
    "                if cur == ')':\n",
    "                    tmp = dfs()\n",
    "                    for k, v in tmp.items():\n",
    "                        res[k] += v * int(cnt) if cnt else v\n",
    "                    cnt = ''  # reset cnt\n",
    "                if cur == '(':\n",
    "                    break\n",
    "            return res\n",
    "        \n",
    "        idx = 0\n",
    "        formula = formula[::-1]\n",
    "        n = len(formula)\n",
    "        res = dfs()\n",
    "        return ''.join(k + (str(v) if v > 1 else '') for k, v in sorted(res.items()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "\n",
    "        def dfs(s):\n",
    "            ans = defaultdict(int)\n",
    "            if not s:\n",
    "                return ans\n",
    "            i = 0\n",
    "            while i < len(s):\n",
    "                if s[i].isupper():\n",
    "                    j = i + 1\n",
    "                    while j < len(s) and s[j].islower():\n",
    "                        j += 1\n",
    "                    name = s[i:j]\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t*10 + int(s[j])\n",
    "                        j += 1\n",
    "                    ans[name] += max(t,1)\n",
    "                    i = j\n",
    "                else:\n",
    "                    cnt = 1\n",
    "                    j = i + 1\n",
    "                    while cnt:\n",
    "                        if s[j] == '(':\n",
    "                            cnt += 1\n",
    "                        if s[j] == ')':\n",
    "                            cnt -= 1\n",
    "                        j += 1\n",
    "                    nxt = dfs(s[i + 1:j - 1])\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t*10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(t,1)\n",
    "                    for k,v in nxt.items():\n",
    "                        ans[k] += v*t\n",
    "                    i = j\n",
    "            return ans\n",
    "        \n",
    "        ans = ''\n",
    "        for k,v in sorted(dfs(formula).items()):\n",
    "            ans += k if v == 1 else k + str(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countOfAtoms(self, formula: str) -> str:\n",
    "#         res = dict()\n",
    "#         stack = []\n",
    "#         brace_stack = []\n",
    "#         n = len(formula)\n",
    "#         cnt = \"\"\n",
    "        \n",
    "#         i = 0\n",
    "#         atom = \"\"\n",
    "#         while i <= n - 1: \n",
    "#             if formula[i].isupper(): \n",
    "#                 atom = formula[i]\n",
    "#                 i += 1\n",
    "#             while i < n and formula[i].islower():\n",
    "#                 atom += formula[i]\n",
    "#                 i += 1\n",
    "                \n",
    "#             if i <= n - 1 and formula[i].isdigit():\n",
    "#                 cnt = formula[i]\n",
    "#                 i += 1\n",
    "#                 while i < n and formula[i].isdigit():\n",
    "#                     cnt += formula[i]\n",
    "#                     i += 1\n",
    "#                 stack.append((atom, int(cnt), len(brace_stack)))\n",
    "#             while i <= n - 1 and formula[i] == \"(\":\n",
    "#                 brace_stack.append(formula)\n",
    "#                 if len(atom) and int(cnt) == 0:\n",
    "#                     stack.append((atom, 1, len(brace_stack)))\n",
    "#                 atom = \"\"\n",
    "#                 cnt = \"\"\n",
    "#                 i += 1\n",
    "\n",
    "#             while i <= n - 1 and formula[i] == \")\":  \n",
    "#                 while i <= n - 1 and formula[i].isdigit():\n",
    "#                     cnt = int(cnt)\n",
    "#                     cnt *= formula[i]\n",
    "#                     i += 1\n",
    "#                 brace_stack.pop()\n",
    "                    \n",
    "                    \n",
    "#                 num = cnt  \n",
    "#                 for ele in stack:\n",
    "#                     res[ele[0]] += ele[1]\n",
    "#            return res\n",
    "\n",
    "                    \n",
    "                    \n",
    "class Solution:\n",
    "    def countOfAtoms(self, f: str) -> str:\n",
    "        i = 0\n",
    "        n = len(f)\n",
    "        element_info = list()   # list of [element_name, number_of_element, number_of_parentheses]\n",
    "        parentheses_stack = list()\n",
    "        # atom = str()\n",
    "        distribution = dict()\n",
    "        while i < n:\n",
    "            # 如果遇到的是字母\n",
    "            # 如果遇到的是大写字母\n",
    "            atom = str()\n",
    "            if f[i].isupper():\n",
    "                atom = f[i]\n",
    "                i += 1\n",
    "            # 跟着小写字母\n",
    "            while i < n and f[i].islower():\n",
    "                atom += f[i]\n",
    "                i += 1\n",
    "            cnt = str()\n",
    "            # 如果后面有数\n",
    "            if i < n and f[i].isdigit():\n",
    "                # 遍历所有的数\n",
    "                while i < n and f[i].isdigit():\n",
    "                    cnt += f[i]\n",
    "                    i += 1\n",
    "                element_info.append([atom, int(cnt), len(parentheses_stack)])\n",
    "            # 如果后面没有数\n",
    "            else:\n",
    "                # 如果前面的if都执行过（即得到了某一个atom，而不是一开始就从(开头）\n",
    "                # print(\"i, atom:\", i, atom)\n",
    "                if len(atom) and len(cnt) == 0:\n",
    "                    element_info.append([atom, 1, len(parentheses_stack)])\n",
    "                if i < n and f[i] == '(':\n",
    "                    parentheses_stack.append('(')\n",
    "                    i += 1\n",
    "                elif i < n and f[i] == ')':\n",
    "                    i += 1\n",
    "                    cnt = str()\n",
    "                    if i < n and f[i].isdigit():\n",
    "                        # 遍历所有的数\n",
    "                        while i < n and f[i].isdigit():\n",
    "                            cnt += f[i]\n",
    "                            i += 1\n",
    "                        cnt = int(cnt)\n",
    "                    else: cnt = 1\n",
    "                    # parentheses_stack.pop()\n",
    "                    for k in range(len(element_info)-1,-1,-1):\n",
    "                        if element_info[k][2] == len(parentheses_stack):\n",
    "                            element_info[k][1] *= cnt\n",
    "                            element_info[k][2] -= 1\n",
    "                        else:\n",
    "                            break\n",
    "                    parentheses_stack.pop()\n",
    "        \n",
    "        # print(element_info)\n",
    "        for ele in element_info:\n",
    "            if ele[0] in distribution:\n",
    "                distribution[ele[0]] += ele[1]\n",
    "            else:\n",
    "                distribution[ele[0]] = ele[1]\n",
    "\n",
    "        # print(distribution)\n",
    "        lst = sorted(distribution.items(), key=lambda obj: obj[0])\n",
    "        # print(lst)\n",
    "        ans = str()\n",
    "        for name, number in lst:\n",
    "            if number == 1:\n",
    "                ans += name\n",
    "            else:\n",
    "                ans += name + str(number)\n",
    "        return ans\n",
    "           \n",
    "                    \n",
    "            \n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    x = formula[pose]\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #大写\n",
    "    if x.isupper():\n",
    "        #有小写\n",
    "        while i<len(formula) and formula[i].islower():\n",
    "            i+=1\n",
    "        element = formula[pose:i]\n",
    "        #有数字\n",
    "        start_num = i\n",
    "        while i<len(formula) and formula[i].isdigit():\n",
    "            i+=1\n",
    "            flag = True\n",
    "        if flag:\n",
    "            if element not in dic:\n",
    "                dic[element] = int(formula[start_num:i])\n",
    "            else:\n",
    "                dic[element] += int(formula[start_num:i])\n",
    "        else:\n",
    "            if element not in dic:\n",
    "                dic[element] = 1\n",
    "            else:\n",
    "                dic[element] += 1\n",
    "    return i\n",
    "\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose + 1, dic\n",
    "\n",
    "        x = formula[pose]\n",
    "        if x == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose+=1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose,dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0 )\n",
    "\n",
    "        lst = sorted(dic.items(), key=lambda x: x[0])\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    ch = formula[pose]\n",
    "    assert ch.isupper()\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #有小写\n",
    "    while  i<len(formula) and formula[i].islower():\n",
    "        i+=1\n",
    "    element = formula[pose:i]\n",
    "    #有数字\n",
    "    start_num = i\n",
    "    while i<len(formula) and formula[i].isdigit():\n",
    "        i += 1\n",
    "        flag = True\n",
    "    if flag:\n",
    "        if element not in dic:\n",
    "            dic[element] = int(formula[start_num:i])\n",
    "        else:\n",
    "            dic[element] += int(formula[start_num:i])\n",
    "    else:\n",
    "        if element not in dic:\n",
    "            dic[element] = 1\n",
    "        else:\n",
    "            dic[element] += 1\n",
    "    return i\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose, dic\n",
    "\n",
    "        ch = formula[pose]\n",
    "        if ch == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            assert formula[pose] == ')'\n",
    "            pose+=1\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose += 1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose, dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        assert pos == len(formula)\n",
    "        lst = sorted(dic.items(), key=lambda x: x[0])\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    ch = formula[pose]\n",
    "    assert ch.isupper()\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #有小写\n",
    "    while  i<len(formula) and formula[i].islower():\n",
    "        i+=1\n",
    "    element = formula[pose:i]\n",
    "    #有数字\n",
    "    start_num = i\n",
    "    while i<len(formula) and formula[i].isdigit():\n",
    "        i += 1\n",
    "        flag = True\n",
    "    if flag:\n",
    "        if element not in dic:\n",
    "            dic[element] = int(formula[start_num:i])\n",
    "        else:\n",
    "            dic[element] += int(formula[start_num:i])\n",
    "    else:\n",
    "        if element not in dic:\n",
    "            dic[element] = 1\n",
    "        else:\n",
    "            dic[element] += 1\n",
    "    return i\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose, dic\n",
    "\n",
    "        ch = formula[pose]\n",
    "        if ch == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            assert formula[pose] == ')'\n",
    "            pose+=1\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose += 1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose, dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        assert pos == len(formula)\n",
    "        lst = sorted(dic.items())\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        def lt726(formula):\n",
    "            def parse(l):\n",
    "                d=defaultdict(int)\n",
    "                ele_stack,num_stack,d_stack=[],[],[]\n",
    "                for item in l:\n",
    "                    if type(item) is str:\n",
    "                        if ord('A')<=ord(item)<=ord('Z'):\n",
    "                            if ele_stack:\n",
    "                                ele=''.join(ele_stack)\n",
    "                                num=int(''.join(num_stack)) if num_stack else 1\n",
    "                                d[ele]+=num\n",
    "                                ele_stack=[]\n",
    "                            if d_stack:\n",
    "                                mul=int(''.join(num_stack)) if num_stack else 1\n",
    "                                for k,v in d_stack.pop().items():d[k]+=v*mul\n",
    "                                d_stack=[]\n",
    "                            num_stack=[]\n",
    "                            ele_stack.append(item)\n",
    "                        elif ord('a')<=ord(item)<=ord('z'):\n",
    "                            ele_stack.append(item)\n",
    "                        else:num_stack.append(item)\n",
    "                    else:\n",
    "                        if ele_stack:\n",
    "                            ele = ''.join(ele_stack)\n",
    "                            num = int(''.join(num_stack)) if num_stack else 1\n",
    "                            d[ele] += num\n",
    "                            ele_stack = []\n",
    "                        if d_stack:\n",
    "                            mul = int(''.join(num_stack)) if num_stack else 1\n",
    "                            for k, v in d_stack.pop().items(): d[k] += v * mul\n",
    "                            d_stack = []\n",
    "                        num_stack = []\n",
    "                        d_stack.append(item)\n",
    "\n",
    "                if ele_stack:\n",
    "                    ele = ''.join(ele_stack)\n",
    "                    num = int(''.join(num_stack)) if num_stack else 1\n",
    "                    d[ele] += num\n",
    "                if d_stack:\n",
    "                    mul = int(''.join(num_stack)) if num_stack else 1\n",
    "                    for k, v in d_stack.pop().items(): d[k] += v * mul\n",
    "                return d\n",
    "            stack=[]\n",
    "            for ch in formula:\n",
    "                if ch!=')':stack.append(ch)\n",
    "                else:\n",
    "                    ptr=len(stack)-1\n",
    "                    while stack[ptr]!='(':ptr-=1\n",
    "                    temp=stack[ptr+1:]\n",
    "                    stack=stack[:ptr]\n",
    "                    stack.append(parse(temp))\n",
    "            d=parse(stack)\n",
    "            res=[[k,v] for k,v in d.items()]\n",
    "            res.sort(key=lambda x:x[0])\n",
    "            res_s=''\n",
    "            for k,v in res:\n",
    "                res_s+=k\n",
    "                if v>1:res_s+=str(v)\n",
    "            return res_s\n",
    "        return lt726(formula)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    ch = formula[pose]\n",
    "    assert ch.isupper()\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #有小写\n",
    "    while  i<len(formula) and formula[i].islower():\n",
    "        i+=1\n",
    "    element = formula[pose:i]\n",
    "    #有数字\n",
    "    start_num = i\n",
    "    while i<len(formula) and formula[i].isdigit():\n",
    "        i += 1\n",
    "        flag = True\n",
    "    if flag:\n",
    "        if element not in dic:\n",
    "            dic[element] = int(formula[start_num:i])\n",
    "        else:\n",
    "            dic[element] += int(formula[start_num:i])\n",
    "    else:\n",
    "        if element not in dic:\n",
    "            dic[element] = 1\n",
    "        else:\n",
    "            dic[element] += 1\n",
    "    return i\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose, dic\n",
    "\n",
    "        ch = formula[pose]\n",
    "        if ch == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            assert formula[pose] == ')'\n",
    "            pose+=1\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose += 1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose, dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        assert pos == len(formula)\n",
    "        lst = sorted(dic.items())\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        n = len(formula)\n",
    "        i = 0\n",
    "\n",
    "        def get_num():\n",
    "            nonlocal i\n",
    "            if i == n or not formula[i].isdigit():\n",
    "                return 1\n",
    "            num = 0\n",
    "            while i < n and formula[i].isdigit():\n",
    "                num = num * 10 + int(formula[i])\n",
    "                i += 1\n",
    "            return num\n",
    "\n",
    "        def get_atom():\n",
    "            nonlocal i\n",
    "            atom = ''\n",
    "            while True:\n",
    "                atom += formula[i]\n",
    "                i += 1\n",
    "                if i == n or not formula[i].islower():\n",
    "                    break\n",
    "            return atom\n",
    "\n",
    "        stk = [defaultdict(int)]\n",
    "        while i < n:\n",
    "            if formula[i] == '(':\n",
    "                i += 1\n",
    "                stk.append(defaultdict(int))\n",
    "            elif formula[i] == ')':\n",
    "                i += 1\n",
    "                num = get_num()\n",
    "                mp = stk.pop()\n",
    "                for atom, val in mp.items():\n",
    "                    stk[-1][atom] += val * num\n",
    "            else:\n",
    "                atom = get_atom()\n",
    "                num = get_num()\n",
    "                stk[-1][atom] += num\n",
    "\n",
    "        pairs = sorted(stk[-1].items())\n",
    "        ans = ''\n",
    "        for atom, num in pairs:\n",
    "            ans += atom\n",
    "            if num > 1: ans += str(num)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        from collections import defaultdict\n",
    "        def dfs(s):\n",
    "            if not s:\n",
    "                return []\n",
    "            ans = defaultdict(int)\n",
    "            i = 0\n",
    "            n = len(s)\n",
    "            while i < n:\n",
    "                if s[i].isupper():\n",
    "                    j = i + 1\n",
    "                    while j < n and s[j].islower():\n",
    "                        j += 1\n",
    "                    k = s[i:j]\n",
    "                    t = 0\n",
    "                    while j < n and s[j].isdigit():\n",
    "                        t = t * 10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(1,t)\n",
    "                    ans[k] += t            \n",
    "                    i = j\n",
    "                else:\n",
    "                    j,cnt = i + 1,1\n",
    "                    while cnt:\n",
    "                        if s[j] == '(':\n",
    "                            cnt += 1\n",
    "                        if s[j] == ')':\n",
    "                            cnt -= 1\n",
    "                        j += 1\n",
    "                    nxt = dfs(s[i + 1:j - 1])\n",
    "                    t = 0\n",
    "                    while j < n and s[j].isdigit():\n",
    "                        t = t * 10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(1,t)\n",
    "                    for k,v in nxt.items():\n",
    "                        ans[k] += v*t\n",
    "                    i = j\n",
    "            return ans\n",
    "                    \n",
    "        ans = ''\n",
    "        for k,v in sorted(dfs(formula).items()):\n",
    "            ans += k if v == 1 else k + str(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        def base(cem: str):\n",
    "            pre = ''\n",
    "            cem_ = ''\n",
    "            dig_ = ''\n",
    "            dic = defaultdict(int)\n",
    "            for i in cem:\n",
    "                if i.islower():\n",
    "                    if pre.isalpha():\n",
    "                        cem_ += i\n",
    "                    elif pre.isdigit():\n",
    "                        dic[cem_] += int(dig_)\n",
    "                        cem_ = i\n",
    "                    dig_ = ''\n",
    "                    pre = i\n",
    "                elif i.isupper():\n",
    "                    if pre.isalpha():\n",
    "                        dic[cem_] += 1\n",
    "                    elif pre.isdigit():\n",
    "                        dic[cem_] += int(dig_)\n",
    "                    dig_ = ''\n",
    "                    cem_ = i\n",
    "                    pre = i\n",
    "\n",
    "                elif i.isdigit():\n",
    "                    dig_ += i\n",
    "                    pre = i\n",
    "\n",
    "            if cem_:\n",
    "                if dig_:\n",
    "                    dic[cem_] += int(dig_)\n",
    "                else:\n",
    "                    dic[cem_] += 1\n",
    "            return dic\n",
    "\n",
    "        def merge(dic1, dic2):\n",
    "            for key in dic2:\n",
    "                dic1[key] = dic1[key] + dic2[key]\n",
    "            return dic1\n",
    "\n",
    "\n",
    "        def dfs(cem: str, start, end):\n",
    "            i = start\n",
    "            pre = defaultdict(int)\n",
    "            stack = []\n",
    "            while i < end:\n",
    "                if cem[i] in {'[', '('}:\n",
    "                    if stack:\n",
    "                        if pre:\n",
    "                            pre = merge(pre, base(''.join(stack)))\n",
    "                        else:\n",
    "\n",
    "                            pre = base(''.join(stack))\n",
    "                    dic, next_end = dfs(cem, i + 1, end)\n",
    "                    pre = merge(pre, dic)\n",
    "                    i = next_end\n",
    "                    stack.clear()\n",
    "\n",
    "                elif cem[i] in {']', ')'}:\n",
    "                    if not pre:\n",
    "                        inside_dic = base(cem[start: i])\n",
    "                    else:\n",
    "                        if stack:\n",
    "                            inside_dic = merge(pre, base(''.join(stack)))\n",
    "                        else:\n",
    "                            inside_dic = pre\n",
    "                    plus = ''\n",
    "                    next_end = i\n",
    "                    for _ in range(i+1, end):\n",
    "                        if cem[_].isdigit():\n",
    "                            plus += cem[_]\n",
    "                            next_end = _\n",
    "                        else:\n",
    "                            break\n",
    "                    if not plus:\n",
    "                        plus = 1\n",
    "                    return {key: value*int(plus) for key, value in inside_dic.items()}, next_end\n",
    "                else:\n",
    "                    stack.append(cem[i])\n",
    "                i += 1\n",
    "            if stack:\n",
    "                pre = merge(pre, base(''.join(stack)))\n",
    "            _ = sorted(list(pre.items()), key=lambda x: x[0])\n",
    "\n",
    "            return ''.join([i[0]+str(i[1]) if i[1] != 1 else i[0] for i in _])\n",
    "        return dfs(formula, 0, len(formula))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        from collections import defaultdict\n",
    "        def dfs(s):\n",
    "            ans = defaultdict(int)\n",
    "            if not s:\n",
    "                return ans\n",
    "            i = 0\n",
    "            while i < len(s):\n",
    "                if s[i].isupper():\n",
    "                    j = i + 1\n",
    "                    while j < len(s) and s[j].islower():\n",
    "                        j += 1\n",
    "                    name = s[i:j]\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t * 10 + int(s[j])\n",
    "                        j += 1\n",
    "                    ans[name] += max(1,t)\n",
    "                    i = j\n",
    "                else:\n",
    "                    j = i + 1\n",
    "                    cnt= 1\n",
    "                    while cnt:\n",
    "                        if s[j] == '(':\n",
    "                            cnt += 1\n",
    "                        if s[j] == ')':\n",
    "                            cnt -= 1\n",
    "                        j += 1\n",
    "                    nxt = dfs(s[i + 1:j - 1])\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t * 10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(t,1)\n",
    "                    for k,v in nxt.items():\n",
    "                        ans[k] += v*t\n",
    "                    i = j\n",
    "            return ans\n",
    "        res = dfs(formula)\n",
    "        ans = ''\n",
    "        for k,v in sorted(res.items()):\n",
    "            ans += k if v == 1 else k + str(v)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        def dfs(s):\n",
    "            ans = defaultdict(int)\n",
    "            if not s:\n",
    "                return ans\n",
    "            i = 0\n",
    "            n = len(s)\n",
    "            while i < n:\n",
    "                if s[i].isupper():\n",
    "                    j = i + 1\n",
    "                    while j < len(s) and s[j].islower():\n",
    "                        j += 1\n",
    "                    k = s[i:j]\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t * 10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(t,1)\n",
    "                    ans[k] += t\n",
    "                    i = j\n",
    "                else:\n",
    "                    cnt = 1\n",
    "                    j = i + 1\n",
    "                    while cnt:\n",
    "                        if s[j] == '(':\n",
    "                            cnt += 1\n",
    "                        if s[j] ==')':\n",
    "                            cnt -= 1\n",
    "                        j += 1\n",
    "                    nxt = dfs(s[i + 1:j - 1])\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t * 10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(t,1)\n",
    "                    for k,v in nxt.items():\n",
    "                        ans[k] += v*t\n",
    "                    i = j\n",
    "            return ans\n",
    "        ans = ''\n",
    "        for k,v in sorted(dfs(formula).items()):\n",
    "            ans += k if v == 1 else k + str(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "\n",
    "        def dfs(s):\n",
    "            if not s:\n",
    "                return {}\n",
    "            ans = defaultdict(int)\n",
    "            i = 0\n",
    "            while i < len(s):\n",
    "                if s[i].isupper(): # 大写字母\n",
    "                    j = i + 1\n",
    "                    # 小写字母\n",
    "                    while j < len(s) and s[j].islower():\n",
    "                        j += 1\n",
    "                    name = s[i:j]\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t*10 + int(s[j])\n",
    "                        j += 1\n",
    "                    ans[name] += max(1,t)\n",
    "                    i = j\n",
    "                elif s[i] == '(':\n",
    "                    cnt = 1\n",
    "                    j = i + 1\n",
    "                    while j < len(s):\n",
    "                        if s[j] == '(':\n",
    "                            cnt += 1\n",
    "                        if s[j] == ')':\n",
    "                            cnt -= 1\n",
    "                            if cnt == 0:\n",
    "                                break\n",
    "                        j += 1\n",
    "                    cnts = dfs(s[i + 1:j])\n",
    "                    j += 1\n",
    "                    # 括号后数字\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t * 10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(t,1)\n",
    "                    for k,v in cnts.items():\n",
    "                        ans[k] += v*t\n",
    "                    i = j\n",
    "            return ans\n",
    "        a = list(dfs(formula).items())\n",
    "        a.sort()\n",
    "        ans = ''\n",
    "        for k,v in a:\n",
    "            if v > 1:\n",
    "                ans += k + str(v)\n",
    "            else:\n",
    "                ans += k\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stack = []\n",
    "        nowdict = {}\n",
    "        idx = 0\n",
    "        lenf = len(formula)\n",
    "        while idx < lenf:\n",
    "            if formula[idx] == '(':\n",
    "                stack.append(nowdict)\n",
    "                nowdict = {}\n",
    "                idx += 1\n",
    "            elif formula[idx] == ')':\n",
    "                num = 1\n",
    "                if idx+1 < lenf and formula[idx+1].isdigit():\n",
    "                    l = r = idx + 1\n",
    "                    while r < lenf and formula[r].isdigit():\n",
    "                        r += 1\n",
    "                    num = int(formula[l:r])\n",
    "                    idx = r - 1\n",
    "                idx += 1\n",
    "                for item in nowdict:\n",
    "                    nowdict[item] *= num\n",
    "                if stack:\n",
    "                    predict = stack[-1]\n",
    "                    stack.pop()\n",
    "                    for item in nowdict:\n",
    "                        if item not in predict:\n",
    "                            predict[item] = 0\n",
    "                        predict[item] += nowdict[item]\n",
    "                    nowdict = predict\n",
    "            elif formula[idx].isalpha():\n",
    "                l, r = idx, idx+1\n",
    "                while r < lenf and formula[r].islower():\n",
    "                    r += 1\n",
    "                element = formula[l:r]\n",
    "                l = r\n",
    "                while r < lenf and formula[r].isdigit():\n",
    "                    r += 1\n",
    "                num = 1\n",
    "                # print(formula[l:r])\n",
    "                if l < r:\n",
    "                    num = int(formula[l:r])\n",
    "                if element not in nowdict:\n",
    "                    nowdict[element] = 0\n",
    "                nowdict[element] += num\n",
    "                idx = r\n",
    "        ans = ''\n",
    "        # print(nowdict)\n",
    "        elelist = []\n",
    "        for item in nowdict:\n",
    "            elelist.append((item, nowdict[item]))\n",
    "        elelist.sort()\n",
    "        for x,y in elelist:\n",
    "            ans += x\n",
    "            if y != 1:\n",
    "                ans += str(y)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expandOfAtoms(self, formula: str) -> dict:\n",
    "        dic = {}\n",
    "        n=len(formula)\n",
    "        i=0\n",
    "        while i<n:\n",
    "            print(i)\n",
    "            if formula[i].isupper():\n",
    "                j=1\n",
    "                atom = formula[i]\n",
    "                while i+j<n and formula[i+j].islower():\n",
    "                    atom += formula[i+j]\n",
    "                    j += 1\n",
    "                cntStr=''\n",
    "                while i+j<n and formula[i+j].isnumeric():\n",
    "                    cntStr += formula[i+j]\n",
    "                    j += 1\n",
    "                i += j-1\n",
    "\n",
    "                if cntStr == '':\n",
    "                    cnt = 1\n",
    "                else:\n",
    "                    cnt = int(cntStr)\n",
    "                \n",
    "                if atom in dic:\n",
    "                    dic[atom] += cnt\n",
    "                else:\n",
    "                    dic[atom] = cnt\n",
    "                \n",
    "            if formula[i] == '(':\n",
    "                nP=1\n",
    "                sTmp = ''\n",
    "                cntStr = ''\n",
    "                j=1\n",
    "                while nP>0:\n",
    "                    if i+j<n and formula[i+j] == '(':\n",
    "                        nP += 1\n",
    "                        sTmp += formula[i+j]\n",
    "                    elif i+j<n and formula[i+j] == ')':\n",
    "                        nP -= 1\n",
    "                        if nP>0:\n",
    "                            sTmp += formula[i+j]\n",
    "                    else:\n",
    "                        sTmp += formula[i+j]\n",
    "                    j += 1\n",
    "                while i+j<n and formula[i+j].isnumeric():\n",
    "                    cntStr += formula[i+j]\n",
    "                    j += 1\n",
    "                i += j-1\n",
    "                if cntStr == '':\n",
    "                    cnt = 1\n",
    "                else:\n",
    "                    cnt = int(cntStr)\n",
    "\n",
    "                dicTmp = self.expandOfAtoms(sTmp)\n",
    "                for atom in dicTmp.keys():\n",
    "                    if atom in dic:\n",
    "                        dic[atom] += cnt * dicTmp[atom]\n",
    "                    else:\n",
    "                        dic[atom] = cnt * dicTmp[atom]\n",
    "        \n",
    "                \n",
    "            i += 1\n",
    "\n",
    "\n",
    "        return dic\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return dic\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        dic = self.expandOfAtoms(formula)\n",
    "\n",
    "        s = ''\n",
    "        for atom in sorted(dic):\n",
    "            s += atom\n",
    "            if dic[atom]>1:\n",
    "                s += str(dic[atom])\n",
    "        \n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        stack = [collections.defaultdict(int)]\n",
    "        i = 0\n",
    "\n",
    "        def parseInt():\n",
    "            nonlocal i \n",
    "\n",
    "            start = i\n",
    "            while i < len(formula) and formula[i].isdigit():\n",
    "                i += 1\n",
    "            \n",
    "            ss = formula[start:i]\n",
    "\n",
    "            if not ss:\n",
    "                return 1\n",
    "            else:\n",
    "                return int(ss)\n",
    "\n",
    "        def parseAtom():\n",
    "            nonlocal i\n",
    "            start = i \n",
    "            # while i < len(formula) and ('a' <= formula[i] <= 'z' or 'A' <= formula[i] <= 'Z'):\n",
    "            #     i += 1\n",
    "\n",
    "            # ss = formula[start:i]\n",
    "            i += 1\n",
    "            while i < len(formula) and 'a' <= formula[i] <= 'z':\n",
    "                i += 1\n",
    "            \n",
    "            ss = formula[start:i]\n",
    "\n",
    "            return ss \n",
    "\n",
    "        while i < len(formula):\n",
    "            if formula[i] == '(':\n",
    "                stack.append(collections.defaultdict(int))\n",
    "                i += 1\n",
    "            elif formula[i] == ')':\n",
    "                i += 1\n",
    "                mul = parseInt()\n",
    "\n",
    "                tmp = stack.pop()\n",
    "                for key in tmp.keys():\n",
    "                    stack[-1][key] += (tmp[key] * mul)\n",
    "\n",
    "            elif 'A' <= formula[i] <= 'Z':\n",
    "                atom = parseAtom()\n",
    "                cnt = parseInt()\n",
    "\n",
    "                tmp = stack[-1]\n",
    "                tmp[atom] = tmp.get(atom, 0) + cnt\n",
    "        \n",
    "        cnts = stack[0]\n",
    "\n",
    "        keys = sorted(cnts.keys())\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for key in keys:\n",
    "            res.append(key)\n",
    "            if cnts[key] != 1:\n",
    "                res.append(str(cnts[key]))\n",
    "        \n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "def hendle_auto(formula, pose, dic):\n",
    "    ch = formula[pose]\n",
    "    assert ch.isupper()\n",
    "    i = pose + 1\n",
    "    flag = False\n",
    "    #有小写\n",
    "    while  i<len(formula) and formula[i].islower():\n",
    "        i+=1\n",
    "    element = formula[pose:i]\n",
    "    #有数字\n",
    "    start_num = i\n",
    "    while i<len(formula) and formula[i].isdigit():\n",
    "        i += 1\n",
    "        flag = True\n",
    "    if flag:\n",
    "        if element not in dic:\n",
    "            dic[element] = int(formula[start_num:i])\n",
    "        else:\n",
    "            dic[element] += int(formula[start_num:i])\n",
    "    else:\n",
    "        if element not in dic:\n",
    "            dic[element] = 1\n",
    "        else:\n",
    "            dic[element] += 1\n",
    "    return i\n",
    "def handle_formula(formula,pose):\n",
    "    dic = {}\n",
    "    while pose < len(formula):\n",
    "        if formula[pose] == ')':\n",
    "            return pose, dic\n",
    "\n",
    "        ch = formula[pose]\n",
    "        if ch == '(':\n",
    "            pose, dic1 = handle_formula(formula, pose+1)\n",
    "            assert formula[pose] == ')'\n",
    "            pose+=1\n",
    "            start_pose = pose\n",
    "            flag = False\n",
    "            while pose < len(formula) and formula[pose].isdigit():\n",
    "                flag = True\n",
    "                pose += 1\n",
    "            if flag:\n",
    "                for v in dic1.keys():\n",
    "                    dic1[v] *= int(formula[start_pose:pose])\n",
    "            dic = Counter(dic) + Counter(dic1)\n",
    "            continue\n",
    "        pose = hendle_auto(formula, pose, dic)\n",
    "    return pose, dic\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        assert pos == len(formula)\n",
    "        lst = sorted(dic.items())\n",
    "        res = ''\n",
    "        for v in lst:\n",
    "            res += v[0]\n",
    "            if v[1]>1:\n",
    "                res += str(v[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        a, _ = self.f(formula, 0)\n",
    "        ans = []\n",
    "        for x in a.keys():\n",
    "            ans.append(x + str(a[x])) if a[x] > 1 else ans.append(x)\n",
    "        return ''.join(sorted(ans))\n",
    "        \n",
    "    def f(self, formula, i):\n",
    "        d = {}\n",
    "        cur = None\n",
    "        while i < len(formula):\n",
    "            if formula[i] == '(':\n",
    "                if isinstance(cur, str):\n",
    "                    self.dict_add(d, cur, 1)\n",
    "                elif isinstance(cur, dict):\n",
    "                    for x in cur.keys():\n",
    "                        self.dict_add(d, x, cur[x])\n",
    "                cur, i = self.f(formula, i+1)\n",
    "                pre = None\n",
    "                num = 0\n",
    "            elif formula[i] == ')':\n",
    "                if isinstance(cur, str):\n",
    "                    self.dict_add(d, cur, 1)\n",
    "                    cur = None\n",
    "                elif isinstance(cur, dict):\n",
    "                    for x in cur.keys():\n",
    "                        self.dict_add(d, x, cur[x])\n",
    "                    cur = None\n",
    "                break\n",
    "            elif ord(formula[i]) <= ord('Z') and ord(formula[i]) >= ord('A'):\n",
    "                if isinstance(cur, str):\n",
    "                    self.dict_add(d, cur, 1)\n",
    "                elif isinstance(cur, dict):\n",
    "                    for x in cur.keys():\n",
    "                        self.dict_add(d, x, cur[x])\n",
    "                cur = formula[i]\n",
    "                pre = None\n",
    "                num = 0\n",
    "            elif ord(formula[i]) <= ord('z') and ord(formula[i]) >= ord('a'):\n",
    "                cur += formula[i]\n",
    "                pre = None\n",
    "                num = 0\n",
    "            else:\n",
    "                if num != 0:\n",
    "                    if isinstance(pre, dict):\n",
    "                        prenum = num\n",
    "                        num = num*10 + int(formula[i])\n",
    "                        for x in pre.keys():\n",
    "                            self.dict_add(d, x, -pre[x]*prenum)\n",
    "                            self.dict_add(d, x, pre[x]*num)\n",
    "                    elif isinstance(pre, str):\n",
    "                        self.dict_add(d, pre, -num)\n",
    "                        num = num*10 + int(formula[i])\n",
    "                        self.dict_add(d, pre, num)\n",
    "                else:\n",
    "                    if isinstance(cur, dict):\n",
    "                        for x in cur.keys():\n",
    "                            self.dict_add(d, x, cur[x]*int(formula[i]))\n",
    "                    elif isinstance(cur, str):\n",
    "                        self.dict_add(d, cur, int(formula[i]))\n",
    "                    pre = cur\n",
    "                    num = int(formula[i])\n",
    "                    cur = None\n",
    "            i += 1\n",
    "        if isinstance(cur, str):\n",
    "            self.dict_add(d, cur, 1)\n",
    "        elif isinstance(cur, dict):\n",
    "            for x in cur.keys():\n",
    "                self.dict_add(d, x, cur[x])\n",
    "        return d, i\n",
    "    \n",
    "    def dict_add(self, d, var, n):\n",
    "        if var in d.keys():\n",
    "            d[var] += n\n",
    "        else:\n",
    "            d[var] = n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        n = len(formula)\n",
    "        formula = formula + '#'\n",
    "        i = 0\n",
    "        s = []\n",
    "        while i < n:\n",
    "            if formula[i].isalpha():\n",
    "                j = i + 1\n",
    "                while j <= n and formula[j].isalpha() and formula[j].islower():\n",
    "                    j += 1\n",
    "                atom = formula[i: j]\n",
    "                i = j\n",
    "                if formula[j].isdigit():\n",
    "                    k = j + 1\n",
    "                    while formula[k].isdigit():\n",
    "                        k += 1\n",
    "                    num = int(formula[j: k])\n",
    "                    s.append([atom, num])\n",
    "                    i = k\n",
    "                else:\n",
    "                    s.append([atom, 1])\n",
    "                \n",
    "            elif formula[i] == '(':\n",
    "                s.append('(')\n",
    "                i += 1\n",
    "            elif formula[i] == ')':\n",
    "                j = i + 1\n",
    "                while j <= n and formula[j].isdigit():\n",
    "                    j += 1\n",
    "                num = int(formula[i + 1: j]) if j > i + 1 else 1\n",
    "                i = j\n",
    "                t = []\n",
    "                while s[-1] != '(':\n",
    "                    op = s.pop()\n",
    "                    op[1] = op[1] * num\n",
    "                    t.append(op)\n",
    "                s.pop()\n",
    "                while t:\n",
    "                    s.append(t.pop())\n",
    "            else:\n",
    "                break\n",
    "        d = defaultdict(int)\n",
    "        for atom, num in s:\n",
    "            d[atom] += num\n",
    "        ans = ''\n",
    "        for atom in sorted(d.keys()):\n",
    "            num = d[atom]\n",
    "            if num == 1:\n",
    "                ans += atom\n",
    "            else:\n",
    "                ans += '%s%d' % (atom,num)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        counter=self.count(formula)\n",
    "        keys=list(counter.keys())\n",
    "        keys.sort()\n",
    "        return ''.join([f'{key}{counter[key] if counter[key]>1 else \"\"}' for key in keys])\n",
    "\n",
    "    def count(self, formula: str) -> Counter:\n",
    "        n=len(formula)\n",
    "        def get_num(idx):\n",
    "            num=0\n",
    "            i=idx\n",
    "            while i<n and formula[i].isdigit():\n",
    "                num=10*num+int(formula[i])\n",
    "                i+=1\n",
    "            return num if num else 1,i\n",
    "        def get_el(idx):\n",
    "            # print('@',formula,idx)\n",
    "            assert formula[idx].isupper()\n",
    "            i=idx+1\n",
    "            while i<n and formula[i].islower():\n",
    "                i+=1\n",
    "            return formula[idx:i],i\n",
    "        \n",
    "        def get_idx2(idx1):\n",
    "            t1=idx1\n",
    "            assert formula[idx1]=='('\n",
    "            cnt=1\n",
    "            while cnt>0:\n",
    "                t2=formula.find(')',t1+1)\n",
    "                # print('t2',t2,t1)\n",
    "                t1=formula.find('(',t1+1)\n",
    "                # print('t1',t1)\n",
    "                if t1==-1 or t2<t1:\n",
    "                    cnt-=1\n",
    "                    t1=t2\n",
    "                else:\n",
    "                    t1=t1\n",
    "                    cnt+=1\n",
    "            #     print('cnt',cnt)\n",
    "            # print('get idx2', formula, idx1, t1,t2,formula[t2:])\n",
    "            return t2\n",
    "        if '(' not in formula:\n",
    "            counter=Counter()\n",
    "            idx=0\n",
    "            while idx<n:\n",
    "                el,idx=get_el(idx)\n",
    "                # # print('#@',formula,el,idx)\n",
    "                num,idx=get_num(idx)\n",
    "                # # print('#',formula,num,idx)\n",
    "                counter[el]+=num\n",
    "            return counter\n",
    "        # print('!',formula)\n",
    "        idx1=formula.find('(')\n",
    "        idx2=get_idx2(idx1)\n",
    "\n",
    "        num,idx=get_num(idx2+1)\n",
    "        # print(num,idx)\n",
    "        # print('!!!',formula,'l',formula[:idx1],'m',formula[idx1+1:idx2],'r',formula[idx:])\n",
    "        counter_m = self.count(formula[idx1+1:idx2])\n",
    "        counter_l = self.count(formula[:idx1])\n",
    "        counter_r = self.count(formula[idx:])\n",
    "        for k,v in counter_m.items():\n",
    "            counter_m[k]=v*num\n",
    "        return counter_m+counter_l+counter_r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 大小写要区分，大写是新的开始，小写则是伴随\n",
    "    # 大写字母和 '(' 意味着新的统计量出现，即前面的该加入了\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        where = 0\n",
    "        mp = self.decode(formula, 0)\n",
    "        return self.printOut(mp)\n",
    "    \n",
    "    def decode(self, s: str, i: int) -> dict:\n",
    "        ans = dict()   # 总表\n",
    "        pre = dict()  # 之前收集到的有序表\n",
    "        name = \"\"     # 收集到的元素字母\n",
    "        cnt = 0\n",
    "        while i < len(s) and s[i] != ')':\n",
    "            if s[i].isupper() or s[i] == '(':  # 遇到了大写字母或左括号\n",
    "                self.push(ans, pre, name, cnt)\n",
    "                name = \"\"\n",
    "                pre.clear()\n",
    "                cnt = 0\n",
    "                if s[i].isalpha():\n",
    "                    name += s[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    pre = self.decode(s, i + 1)\n",
    "                    i = self.where + 1\n",
    "            elif s[i].isdigit():\n",
    "                cnt = cnt * 10 + int(s[i])\n",
    "                i += 1\n",
    "            else:  # 小写字母，前面一定跟着大写字母\n",
    "                name += s[i]\n",
    "                i += 1\n",
    "        self.push(ans, pre, name, cnt)   # 最后遍历完后结算\n",
    "        self.where = i\n",
    "        return ans\n",
    "    \n",
    "    # 加入总表\n",
    "    def push(self, ans: dict, mp: dict, name: str, cnt: int) -> None:\n",
    "        # print(name, mp, cnt)\n",
    "        if len(name) > 0 or mp:\n",
    "            cnt = 1 if cnt == 0 else cnt   # 对于0其实对应的就是1\n",
    "            if len(name) > 0:\n",
    "                if name in ans.keys():\n",
    "                    ans[name] += cnt\n",
    "                else:\n",
    "                    ans[name] = cnt\n",
    "            else:\n",
    "                for k, v in mp.items():\n",
    "                    if k in ans.keys():\n",
    "                        ans[k] += v * cnt\n",
    "                    else:\n",
    "                        ans[k] = v * cnt\n",
    "    \n",
    "    # dict()按照字典序输出\n",
    "    def printOut(self, ans: dict) -> str:\n",
    "        lst = sorted(list(ans.keys()))\n",
    "        print(lst)\n",
    "        path = \"\"\n",
    "        for l in lst:\n",
    "            path += l\n",
    "            if ans[l] > 1:\n",
    "                path += str(ans[l])\n",
    "        return path\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def handle_formula(formula, pos):\n",
    "    dic = {}\n",
    "    while pos < len(formula):\n",
    "        if formula[pos] == ')':#遇到右括号\n",
    "            return pos + 1, dic#位置加1，返回括号\n",
    "        x = formula[pos]\n",
    "        if x == '(':#遇到左括号\n",
    "            pos, dic1 = handle_formula(formula, pos+1)\n",
    "            num, pos = handle_num(formula, pos)\n",
    "            for v in dic1.keys():\n",
    "                if num == 0:\n",
    "                    continue\n",
    "                dic1[v] *= num\n",
    "            add_to_dic(dic, dic1)\n",
    "        else:\n",
    "            pos = handle_atom(formula, pos, dic)\n",
    "    # 检查是否有数量为0的元素，如果有，从字典中删除它们\n",
    "    for key in list(dic.keys()):\n",
    "        if dic[key] == 0:\n",
    "            dic[key] = 1\n",
    "    return pos, dic\n",
    "\n",
    "\n",
    "    return pos, dic\n",
    "\n",
    "def add_to_dic(dic, dic1):\n",
    "    for v in dic1.keys():\n",
    "        num = dic.get(v, 0)\n",
    "        # print(num)\n",
    "        num += dic1[v]\n",
    "        dic[v] = num\n",
    "\n",
    "def handle_atom(formula, pos, dic):\n",
    "    x = formula[pos]\n",
    "    assert x.isupper()\n",
    "    savpos = pos\n",
    "    pos += 1\n",
    "    while pos < len(formula) and formula[pos].islower():\n",
    "        pos += 1\n",
    "    element = formula[savpos:pos]\n",
    "    # print(element)\n",
    "    if pos < len(formula) and formula[pos].isdigit():\n",
    "        num, pos = handle_num(formula, pos)\n",
    "    else:\n",
    "        num = 1\n",
    "\n",
    "    dic[element] =dic.get(element,0) +num\n",
    "    # print(dic)\n",
    "    return pos\n",
    "\n",
    "def handle_num(formula, pos):\n",
    "    num = 0\n",
    "    while pos < len(formula) and formula[pos].isdigit():#检查边界并且检查当且字符是否是数字\n",
    "        print(int(formula[pos]))\n",
    "        num = num*10 + int(formula[pos])\n",
    "        pos += 1\n",
    "    return num, pos\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str):\n",
    "        pos, dic = handle_formula(formula, 0)\n",
    "        assert pos == len(formula)\n",
    "\n",
    "\n",
    "        # print(dic)\n",
    "        lst = list(dic.keys())\n",
    "        lst.sort()\n",
    "\n",
    "        res = ''\n",
    "        for s in lst:\n",
    "            num = dic[s]\n",
    "            if num == 1:\n",
    "                res += s\n",
    "            else:\n",
    "                res += f\"{s}{num}\"\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        recursion_dict = {}\n",
    "        def countofatoms_recursion(formula):\n",
    "            result = dict()\n",
    "            i = 0\n",
    "            a = b = None\n",
    "            cur_num = 0\n",
    "            cur_str = ''\n",
    "            r = None\n",
    "            count = 0\n",
    "            if formula in recursion_dict:\n",
    "                return recursion_dict[formula]\n",
    "            while i < len(formula):\n",
    "\n",
    "                if formula[i].isdecimal():\n",
    "                    cur_num = cur_num * 10 + int(formula[i])\n",
    "                    if i == len(formula) - 1:\n",
    "                        if cur_str:\n",
    "                            if cur_str in result:\n",
    "                                result[cur_str] += max(cur_num, 1)\n",
    "                            else:\n",
    "                                result[cur_str] = max(cur_num, 1)\n",
    "                        else:\n",
    "                            for cur_str_k, cur_num_v in r.items():\n",
    "                                if cur_str_k in result:\n",
    "                                    result[cur_str_k] += max(cur_num, 1) * cur_num_v\n",
    "                                else:\n",
    "                                    result[cur_str_k] = max(cur_num, 1) * cur_num_v\n",
    "                elif formula[i] == '(':\n",
    "                    if cur_str:\n",
    "                        if cur_str in result:\n",
    "                            result[cur_str] += max(cur_num, 1)\n",
    "                        else:\n",
    "                            result[cur_str] = max(cur_num, 1)\n",
    "                        cur_str = ''\n",
    "                        cur_num = 0\n",
    "                    if r:\n",
    "                        for cur_str_k, cur_num_v in r.items():\n",
    "                            if cur_str_k in result:\n",
    "                                result[cur_str_k] += max(cur_num, 1) * cur_num_v\n",
    "                            else:\n",
    "                                result[cur_str_k] = max(cur_num, 1) * cur_num_v\n",
    "                        r = None\n",
    "                        cur_num = 0\n",
    "                    if count == 0:\n",
    "                        a = i\n",
    "                    count += 1\n",
    "                elif formula[i] == ')':\n",
    "                    count -= 1\n",
    "                    if count == 0:\n",
    "                        b = i\n",
    "                elif a is None and b is None:\n",
    "                    if cur_str and not ord('a') <= ord(formula[i]) <= ord('z'):\n",
    "\n",
    "                        if cur_str in result:\n",
    "                            result[cur_str] += max(cur_num, 1)\n",
    "                        else:\n",
    "                            result[cur_str] = max(cur_num, 1)\n",
    "\n",
    "                        cur_str = ''\n",
    "                        cur_num = 0\n",
    "\n",
    "                    if r:\n",
    "                        for cur_str_k, cur_num_v in r.items():\n",
    "                            if cur_str_k in result:\n",
    "                                result[cur_str_k] += max(cur_num, 1) * cur_num_v\n",
    "                            else:\n",
    "                                result[cur_str_k] = max(cur_num, 1) * cur_num_v\n",
    "                        r = None\n",
    "                        cur_num = 0\n",
    "\n",
    "                    if ord('a') <= ord(formula[i]) <= ord('z'):\n",
    "\n",
    "                        cur_str += formula[i]\n",
    "                    else:\n",
    "                        cur_str = formula[i]\n",
    "                    if i == len(formula) - 1:\n",
    "                        if cur_str in result:\n",
    "                            result[cur_str] += 1\n",
    "                        else:\n",
    "                            result[cur_str] = 1\n",
    "\n",
    "                if a is not None and b is not None:\n",
    "\n",
    "                    r = countofatoms_recursion(formula[a + 1:b])\n",
    "                    i = b + 1\n",
    "                    if i == len(formula):\n",
    "                        for cur_str_k, cur_num_v in r.items():\n",
    "                            if cur_str_k in result:\n",
    "                                result[cur_str_k] += max(cur_num, 1) * cur_num_v\n",
    "                            else:\n",
    "                                result[cur_str_k] = max(cur_num, 1) * cur_num_v\n",
    "                    a = b = None\n",
    "\n",
    "                    cur_num = 0\n",
    "                else:\n",
    "                    i += 1\n",
    "            recursion_dict[formula] = result\n",
    "            return result\n",
    "\n",
    "        result = ''\n",
    "        for s, l in sorted(countofatoms_recursion(formula).items(), key=lambda x:x[0]):\n",
    "            result += s\n",
    "            if l > 1:\n",
    "                result += str(l)\n",
    "        return result\n",
    "\n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        i = 0\n",
    "\n",
    "        while i < len(formula):\n",
    "            if formula[i] == '(':\n",
    "                stack.append('(')\n",
    "                i += 1\n",
    "            elif formula[i] == ')':\n",
    "                j = i + 1\n",
    "                mul = None\n",
    "                if j == len(formula):\n",
    "                    mul = 1\n",
    "                    i += 1\n",
    "                elif formula[j].isdigit():\n",
    "                    while j < len(formula) and formula[j].isdigit():\n",
    "                        j += 1\n",
    "                    \n",
    "                    mul = int(formula[i + 1:j])\n",
    "                    i = j\n",
    "                    \n",
    "                else:\n",
    "                    mul = 1\n",
    "                    i += 1\n",
    "                \n",
    "                tmp = []\n",
    "                while stack and stack[-1] != '(':\n",
    "                    val = stack.pop()\n",
    "                    if str(val).isdigit():\n",
    "                        tmp.append(val * mul)\n",
    "                    else:\n",
    "                        tmp.append(val)\n",
    "                \n",
    "                stack.pop()\n",
    "\n",
    "                while tmp:\n",
    "                    stack.append(tmp.pop())\n",
    "\n",
    "            elif 'A' <= formula[i] <= 'Z':\n",
    "                if i + 1 == len(formula) or not ('a' <= formula[i + 1] <= 'z'):\n",
    "                    stack.append(formula[i])\n",
    "\n",
    "                    if i + 1 == len(formula):\n",
    "                        stack.append(1)\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        if formula[i + 1].isdigit():\n",
    "                            j = i + 1\n",
    "\n",
    "                            while j < len(formula) and formula[j].isdigit():\n",
    "                                j += 1\n",
    "                            \n",
    "                            stack.append(int(formula[i + 1:j]))\n",
    "                            i = j\n",
    "                        else:\n",
    "                            stack.append(1)\n",
    "                            i += 1\n",
    "\n",
    "                else:\n",
    "                    j = i + 1\n",
    "                    while j < len(formula) and 'a' <= formula[j] <= 'z':\n",
    "                        j += 1\n",
    "\n",
    "                    stack.append(formula[i : j])\n",
    "                    # i = j\n",
    "                    i = j - 1\n",
    "\n",
    "\n",
    "                    if i + 1 == len(formula):\n",
    "                        stack.append(1)\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        if formula[i + 1].isdigit():\n",
    "                            j = i + 1\n",
    "\n",
    "                            while j < len(formula) and formula[j].isdigit():\n",
    "                                j += 1\n",
    "                            \n",
    "                            stack.append(int(formula[i + 1:j]))\n",
    "                            i = j\n",
    "                        else:\n",
    "                            stack.append(1)\n",
    "                            i += 1\n",
    "\n",
    "\n",
    "\n",
    "        cnts = collections.defaultdict(int)\n",
    "        for i in range(0, len(stack), 2):\n",
    "            cnts[stack[i]] += stack[i + 1]\n",
    "\n",
    "        keys = sorted(cnts.keys())\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for key in keys:\n",
    "            res.append(key)\n",
    "\n",
    "            if cnts[key] == 1:\n",
    "                continue\n",
    "            else:\n",
    "                res.append(str(cnts[key]))\n",
    "\n",
    "        return ''.join(res)\n",
    "\n",
    "                    \n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        \n",
    "        def is_up(x):\n",
    "            return ord('A') <= ord(x) <= ord('Z')\n",
    "\n",
    "        def is_low(x):\n",
    "            return ord('a') <= ord(x) <= ord('z')\n",
    "\n",
    "        def dfs(s):\n",
    "            print(s)\n",
    "            if not s:\n",
    "                return {}\n",
    "            ans = defaultdict(int)\n",
    "            i = 0\n",
    "            while i < len(s):\n",
    "                if is_up(s[i]): # 大写字母\n",
    "                    j = i + 1\n",
    "                    # 小写字母\n",
    "                    while j < len(s) and is_low(s[j]):\n",
    "                        j += 1\n",
    "                    name = s[i:j]\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t*10 + int(s[j])\n",
    "                        j += 1\n",
    "                    ans[name] += max(1,t)\n",
    "                    i = j\n",
    "                elif s[i] == '(':\n",
    "                    cnt = 1\n",
    "                    j = i + 1\n",
    "                    while j < len(s):\n",
    "                        if s[j] == '(':\n",
    "                            cnt += 1\n",
    "                        if s[j] == ')':\n",
    "                            cnt -= 1\n",
    "                            if cnt == 0:\n",
    "                                break\n",
    "                        j += 1\n",
    "                    cnts = dfs(s[i + 1:j])\n",
    "                    j += 1\n",
    "                    # 括号后数字\n",
    "                    t = 0\n",
    "                    while j < len(s) and s[j].isdigit():\n",
    "                        t = t * 10 + int(s[j])\n",
    "                        j += 1\n",
    "                    t = max(t,1)\n",
    "                    for k,v in cnts.items():\n",
    "                        ans[k] += v*t\n",
    "                    i = j\n",
    "            return ans\n",
    "        a = list(dfs(formula).items())\n",
    "        a.sort()\n",
    "        ans = ''\n",
    "        for k,v in a:\n",
    "            if v > 1:\n",
    "                ans += k + str(v)\n",
    "            else:\n",
    "                ans += k\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        recursion_dict = {}\n",
    "        def countofatoms_recursion(formula):\n",
    "            if len(formula) == 1:\n",
    "                return {formula[0] : 1}\n",
    "            result = dict()\n",
    "            i = 0\n",
    "            a = b = None\n",
    "            cur_num = 0\n",
    "            cur_str = ''\n",
    "            r = None\n",
    "            count = 0\n",
    "            if formula in recursion_dict:\n",
    "                return recursion_dict[formula]\n",
    "            while i < len(formula):\n",
    "\n",
    "                if formula[i].isdecimal():\n",
    "                    cur_num = cur_num * 10 + int(formula[i])\n",
    "                    if i == len(formula) - 1:\n",
    "                        if cur_str:\n",
    "                            if cur_str in result:\n",
    "                                result[cur_str] += max(cur_num, 1)\n",
    "                            else:\n",
    "                                result[cur_str] = max(cur_num, 1)\n",
    "                        else:\n",
    "                            for cur_str_k, cur_num_v in r.items():\n",
    "                                if cur_str_k in result:\n",
    "                                    result[cur_str_k] += max(cur_num, 1) * cur_num_v\n",
    "                                else:\n",
    "                                    result[cur_str_k] = max(cur_num, 1) * cur_num_v\n",
    "                elif formula[i] == '(':\n",
    "                    if cur_str:\n",
    "                        if cur_str in result:\n",
    "                            result[cur_str] += max(cur_num, 1)\n",
    "                        else:\n",
    "                            result[cur_str] = max(cur_num, 1)\n",
    "                        cur_str = ''\n",
    "                        cur_num = 0\n",
    "                    if r:\n",
    "                        for cur_str_k, cur_num_v in r.items():\n",
    "                            if cur_str_k in result:\n",
    "                                result[cur_str_k] += max(cur_num, 1) * cur_num_v\n",
    "                            else:\n",
    "                                result[cur_str_k] = max(cur_num, 1) * cur_num_v\n",
    "                        r = None\n",
    "                        cur_num = 0\n",
    "                    if count == 0:\n",
    "                        a = i\n",
    "                    count += 1\n",
    "                elif formula[i] == ')':\n",
    "                    count -= 1\n",
    "                    if count == 0:\n",
    "                        b = i\n",
    "                elif a is None and b is None:\n",
    "                    if cur_str and not ord('a') <= ord(formula[i]) <= ord('z'):\n",
    "\n",
    "                        if cur_str in result:\n",
    "                            result[cur_str] += max(cur_num, 1)\n",
    "                        else:\n",
    "                            result[cur_str] = max(cur_num, 1)\n",
    "\n",
    "                        cur_str = ''\n",
    "                        cur_num = 0\n",
    "\n",
    "                    if r:\n",
    "                        for cur_str_k, cur_num_v in r.items():\n",
    "                            if cur_str_k in result:\n",
    "                                result[cur_str_k] += max(cur_num, 1) * cur_num_v\n",
    "                            else:\n",
    "                                result[cur_str_k] = max(cur_num, 1) * cur_num_v\n",
    "                        r = None\n",
    "                        cur_num = 0\n",
    "\n",
    "                    if ord('a') <= ord(formula[i]) <= ord('z'):\n",
    "\n",
    "                        cur_str += formula[i]\n",
    "                    else:\n",
    "                        cur_str = formula[i]\n",
    "                    if i == len(formula) - 1:\n",
    "                        if cur_str in result:\n",
    "                            result[cur_str] += 1\n",
    "                        else:\n",
    "                            result[cur_str] = 1\n",
    "\n",
    "                if a is not None and b is not None:\n",
    "\n",
    "                    r = countofatoms_recursion(formula[a + 1:b])\n",
    "                    i = b + 1\n",
    "                    if i == len(formula):\n",
    "                        for cur_str_k, cur_num_v in r.items():\n",
    "                            if cur_str_k in result:\n",
    "                                result[cur_str_k] += max(cur_num, 1) * cur_num_v\n",
    "                            else:\n",
    "                                result[cur_str_k] = max(cur_num, 1) * cur_num_v\n",
    "                    a = b = None\n",
    "\n",
    "                    cur_num = 0\n",
    "                else:\n",
    "                    i += 1\n",
    "            recursion_dict[formula] = result\n",
    "            return result\n",
    "\n",
    "        result = ''\n",
    "        for s, l in sorted(countofatoms_recursion(formula).items(), key=lambda x:x[0]):\n",
    "            result += s\n",
    "            if l > 1:\n",
    "                result += str(l)\n",
    "        return result\n",
    "\n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expandAtmos(self, fm:str) -> str:\n",
    "        n=len(fm)\n",
    "        sTmp = ''\n",
    "        nTmp = ''\n",
    "        nRep = 1\n",
    "        s = ''\n",
    "        nP=0\n",
    "        for i in range(n):\n",
    "            if fm[i] == '(':\n",
    "                nP = 1\n",
    "                sTmp = ''\n",
    "                nTmp = ''\n",
    "                j=1\n",
    "                #read content inside ()\n",
    "                while nP>0:\n",
    "                    if fm[i+j] == '(':\n",
    "                        sTmp += fm[i+j]\n",
    "                        nP += 1\n",
    "                    elif fm[i+j] == ')':\n",
    "                        nP -= 1\n",
    "                        if nP>0:\n",
    "                            sTmp += fm[i+j]\n",
    "                    else:\n",
    "                        sTmp += fm[i+j]\n",
    "                    j += 1\n",
    "                i += j-1\n",
    "                \n",
    "                j=1\n",
    "                #read number after ()\n",
    "                while i+j<n and fm[i+j].isnumeric():\n",
    "                    nTmp += fm[i+j]\n",
    "                    j += 1\n",
    "                i += j-1\n",
    "                if nTmp == '':\n",
    "                    nTmp = '1'\n",
    "                \n",
    "                #read sTmp\n",
    "                sTmpNum = ''\n",
    "                nTmpNum = ''\n",
    "                kk=0\n",
    "                while kk < len(sTmp):\n",
    "                    if sTmp[kk].isupper():\n",
    "                        sTmpNum = sTmp[kk]\n",
    "                        nTmpNum = ''\n",
    "                        j=1\n",
    "                        while kk+j < len(sTmp) and sTmp[kk+j].islower():\n",
    "                            sTmpNum += sTmp[kk+j]\n",
    "                            j += 1\n",
    "                        kk += j-1\n",
    "\n",
    "                        j=1\n",
    "                        while kk+j < len(sTmp) and sTmp[kk+j].isnumeric():\n",
    "                            nTmpNum += sTmp[kk+j]\n",
    "                            j += 1\n",
    "                        kk += j-1\n",
    "\n",
    "                        if nTmpNum == '':\n",
    "                            nTmpNum = '1'\n",
    "                    \n",
    "                        s += sTmpNum\n",
    "                        s += str(int(nTmpNum)*int(nTmp))\n",
    "                    \n",
    "                    if sTmp[kk] == '(':\n",
    "                        nP = 1\n",
    "                        sTmpNum = '('\n",
    "                        nTmpNum = ''\n",
    "                        j=1\n",
    "                        #read content inside ()\n",
    "                        while nP>0:\n",
    "                            if sTmp[kk+j] == '(':\n",
    "                                sTmpNum += sTmp[kk+j]\n",
    "                                nP += 1\n",
    "                            elif sTmp[kk+j] == ')':\n",
    "                                nP -= 1\n",
    "                                sTmpNum += sTmp[kk+j]\n",
    "                            else:\n",
    "                                sTmpNum += sTmp[kk+j]\n",
    "                            j += 1\n",
    "                        kk += j\n",
    "                        j=0\n",
    "                        while kk+j < len(sTmp) and sTmp[kk+j].isnumeric():\n",
    "                            nTmpNum += sTmp[kk+j]\n",
    "                            j += 1\n",
    "                        kk += j-1\n",
    "                        if nTmpNum == '':\n",
    "                            nTmpNum = '1'\n",
    "                        s += sTmpNum\n",
    "                        s += str(int(nTmpNum)*int(nTmp))\n",
    "                    kk += 1\n",
    "                        \n",
    "                jtmp = i\n",
    "                break\n",
    "                \n",
    "            else:\n",
    "                s += fm[i]\n",
    "\n",
    "        for j in range(i+1,n):\n",
    "            s += fm[j]\n",
    "\n",
    "        return s\n",
    "\n",
    "\n",
    "\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        dic = {}\n",
    "        dicTmp = {}\n",
    "\n",
    "        while '(' in formula:\n",
    "            formula = self.expandAtmos(formula)\n",
    "        n=len(formula)\n",
    "        sTmp = ''\n",
    "        nTmp = ''\n",
    "        for i in range(n):\n",
    "            if formula[i].isupper():\n",
    "                sTmp = formula[i]\n",
    "                nTmp = ''\n",
    "                j=1\n",
    "                while i+j < n and formula[i+j].islower():\n",
    "                    sTmp += formula[i+j]\n",
    "                    j += 1\n",
    "                i += j-1\n",
    "\n",
    "                j=1\n",
    "                while i+j < n and formula[i+j].isnumeric():\n",
    "                    nTmp += formula[i+j]\n",
    "                    j += 1\n",
    "                i += j-1\n",
    "\n",
    "                if nTmp == '':\n",
    "                    nTmp = '1'\n",
    "                if sTmp in dic:\n",
    "                    dic[sTmp] += int(nTmp)\n",
    "                else:\n",
    "                    dic[sTmp] = int(nTmp)\n",
    "                sTmp = formula[i]\n",
    "        \n",
    "        sorted_dic = {k: dic[k] for k in sorted(dic)}\n",
    "\n",
    "        s = ''\n",
    "        for ii in range(len(sorted_dic)):\n",
    "            s += list(sorted_dic)[ii]\n",
    "            if sorted_dic[list(sorted_dic)[ii]] <2:\n",
    "                continue\n",
    "            s += str(sorted_dic[list(sorted_dic)[ii]])\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        cnt=collections.Counter()\n",
    "        n=len(formula)\n",
    "        s=formula\n",
    "        stack=[]\n",
    "        i=0\n",
    "       # print(\"A\".isUpper)\n",
    "        while i<n:\n",
    "            if s[i]!=\")\":\n",
    "                stack.append(s[i])\n",
    "                i=i+1\n",
    "            elif s[i]==\")\":\n",
    "                cnt=collections.Counter()\n",
    "                k=\"\"\n",
    "                tmp=\"\"\n",
    "                i=i+1\n",
    "                while i<n and s[i].isdigit():\n",
    "                    k=k+s[i]\n",
    "                    i=i+1\n",
    "                while stack and stack[-1]!=\"(\":\n",
    "                    t=stack.pop()\n",
    "                    #print(tmp,t)\n",
    "                    tmp=t+tmp\n",
    "                print(tmp,k)\n",
    "                stack.pop()\n",
    "                j=0\n",
    "                m=len(tmp)\n",
    "                name=\"\"\n",
    "                num=\"\"\n",
    "                while j<m:\n",
    "                    if tmp[j].isupper():\n",
    "                        name=name+tmp[j]\n",
    "                        j=j+1\n",
    "                       # print(tmp[j])\n",
    "                        while j<m and tmp[j].islower():\n",
    "                            name=name+tmp[j]\n",
    "                            j=j+1\n",
    "                        while j<m and tmp[j].isdigit():\n",
    "                            num=num+tmp[j]\n",
    "                            j=j+1\n",
    "                       # print(name,num)\n",
    "                        if len(num)==0:\n",
    "                            num=1\n",
    "                        else:\n",
    "                            num=int(num)\n",
    "                       # print(name)\n",
    "                        cnt[name]+=num\n",
    "                        name=\"\"\n",
    "                        num=\"\"\n",
    "                \n",
    "                if len(k)==0:\n",
    "                    k=1\n",
    "                else:\n",
    "                    k=int(k)\n",
    "                #cnt=cnt\n",
    "                for x in cnt:\n",
    "                    stack.append(x+str(cnt[x]*k))\n",
    "        cnt=collections.Counter()\n",
    "        tmp=\"\".join(stack)\n",
    "        j=0\n",
    "        m=len(tmp)\n",
    "        name=\"\"\n",
    "        num=\"\"\n",
    "        while j<m:\n",
    "            if tmp[j].isupper():\n",
    "                name=name+tmp[j]\n",
    "                j=j+1\n",
    "                # print(tmp[j])\n",
    "                while j<m and tmp[j].islower():\n",
    "                    name=name+tmp[j]\n",
    "                    j=j+1\n",
    "                while j<m and tmp[j].isdigit():\n",
    "                    num=num+tmp[j]\n",
    "                    j=j+1\n",
    "                # print(name,num)\n",
    "                if len(num)==0:\n",
    "                    num=1\n",
    "                else:\n",
    "                    num=int(num)\n",
    "                # print(name)\n",
    "                cnt[name]+=num\n",
    "                name=\"\"\n",
    "                num=\"\"\n",
    "        arr=list(sorted(cnt.items()))\n",
    "        ans=\"\"\n",
    "        for x,n in arr:\n",
    "            if n==1:\n",
    "                ans=ans+x\n",
    "            else:\n",
    "                ans=ans+x+str(n)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOfAtoms(self, formula: str) -> str:\n",
    "        self.where = 0\n",
    "        num_table = {'0':0,'1':1,'2':2,\n",
    "                     '3':3,'4':4,'5':5,\n",
    "                     '6':6,'7':7,'8':8,\n",
    "                     '9':9}\n",
    "        alpha_set = set(['a','b','c','d','e',\n",
    "                    'f','g','h','i','j',\n",
    "                    'k','l','m','n','o',\n",
    "                    'p','q','r','s','t',\n",
    "                    'u','v','w','x','y','z'])\n",
    "        def push(path, str_stack, tmp_stack, cur):\n",
    "            if path!='':\n",
    "                if path in str_stack:\n",
    "                    if cur!=0:\n",
    "                        str_stack[path] += cur\n",
    "                    else:\n",
    "                        str_stack[path] += 1\n",
    "                else:\n",
    "                    if cur!=0:\n",
    "                        str_stack[path] = cur\n",
    "                    else:\n",
    "                        str_stack[path] = 1\n",
    "            else:\n",
    "                for key, value in tmp_stack.items():\n",
    "                    if key in str_stack:\n",
    "                        if cur!=0:\n",
    "                            str_stack[key] += value*cur\n",
    "                        else:\n",
    "                            str_stack[key] += value\n",
    "                    else:\n",
    "                        if cur!=0:\n",
    "                            str_stack[key] = value*cur\n",
    "                        else:\n",
    "                            str_stack[key] = value\n",
    "        def f(s):\n",
    "            str_stack = {}\n",
    "            path = ''\n",
    "            tmp_stack = {}\n",
    "            cur = 0\n",
    "            while self.where!=len(s) and s[self.where]!=')':\n",
    "                if s[self.where] in num_table:\n",
    "                    cur = 10*cur + num_table[s[self.where]]\n",
    "                elif s[self.where]=='(':\n",
    "                    if path:\n",
    "                        push(path, str_stack, {}, cur)\n",
    "                    else:\n",
    "                        push('', str_stack, tmp_stack, cur)\n",
    "                    cur = 0\n",
    "                    path = ''\n",
    "                    self.where += 1\n",
    "                    tmp_stack = f(s)\n",
    "                elif s[self.where] in alpha_set:\n",
    "                    path += s[self.where]\n",
    "                else:\n",
    "                    if path:\n",
    "                        push(path, str_stack, {}, cur)\n",
    "                    else:\n",
    "                        push('', str_stack, tmp_stack, cur)\n",
    "                    cur = 0\n",
    "                    path = s[self.where]\n",
    "                    tmp_stack = {}\n",
    "                self.where += 1\n",
    "            if path:\n",
    "                push(path, str_stack, {}, cur)\n",
    "            else:\n",
    "                push('', str_stack, tmp_stack, cur)\n",
    "            return str_stack\n",
    "        ans = f(formula)\n",
    "        r_ans = []\n",
    "        for key in ans:\n",
    "            if ans[key]!=1:\n",
    "                r_ans.append(key+str(ans[key]))\n",
    "            else:\n",
    "                r_ans.append(key)\n",
    "        r_ans.sort()\n",
    "        return ''.join(r_ans)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
